nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

Position-Based Cryptography and Multiparty Communication Complexity

verfasst von : Joshua Brody, Stefan Dziembowski, Sebastian Faust, Krzysztof Pietrzak

Erschienen in: Theory of Cryptography

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Position based cryptography (PBC), proposed in the seminal work of Chandran, Goyal, Moriarty, and Ostrovsky (SIAM J. Computing, 2014), aims at constructing cryptographic schemes in which the identity of the user is his geographic position. Chandran et al. construct PBC schemes for secure positioning and position-based key agreement in the bounded-storage model (Maurer, J. Cryptology, 1992). Apart from bounded memory, their security proofs need a strong additional restriction on the power of the adversary: he cannot compute joint functions of his inputs. Removing this assumption is left as an open problem.

We show that an answer to this question would resolve a long standing open problem in multiparty communication complexity: finding a function that is hard to compute with low communication complexity in the simultaneous message model, but easy to compute in the fully adaptive model.

On a more positive side: we also show some implications in the other direction, i.e.: we prove that lower bounds on the communication complexity of certain multiparty problems imply existence of PBC primitives. Using this result we then show two attractive ways to “bypass” our hardness result: the first uses the random oracle model, the second weakens the locality requirement in the bounded-storage model to online computability. The random oracle construction is arguably one of the simplest proposed so far in this area. Our results indicate that constructing improved provably secure protocols for PBC requires a better understanding of multiparty communication complexity. This is yet another example where negative results in one area (in our case: lower bounds in multiparty communication complexity) can be used to construct secure cryptographic schemes.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel On the Impossibility of Entropy Reversal, and Its Application to Zero-Knowledge Proofs

Nächstes Kapitel When Does Functional Encryption Imply Obfuscation?

Note that [35] uses the random oracle model, that we use in this work (in Sect. 4.1).

Observe that these assumptions can be made without loss of generality, as storing the computed values does not affect the retrieval bound.

In [16] the security of a key agreement is defined using the “indistinguishability” paradigm (cf. Definition 2.2 in [16]): no adversary, after learning A, should be able to distinguish \(K_{{\mathcal P}}\) from a uniformly random key, with advantage larger than \(\rho \). It is easy to see that these definitions are equivalent.

The reader may object that it is not realistic to assume that an adversary is positioned at zero distance from a verifier. At the end of the proof we argue that \({\mathcal B}_{i}\) can actually be put at some place far from any verifier. We decided to assume that \({\mathcal B}_{i}\) is positioned exactly in point \(\widehat{{\mathcal V}}_{i}\) to keep the exposition simple.

Ambainis, A.: Upper bounds on multiparty communication complexity of shifts. In: Puech, C., Reischuk, R. (eds.) STACS 1996. LNCS, vol. 1046, pp. 631–642. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-60922-9_51 CrossRef

Ambainis, A., Lokam, S.V.: Improved upper bounds on the simultaneous messages complexity of the generalized addressing function. In: Gonnet, G.H., Viola, A. (eds.) LATIN 2000. LNCS, vol. 1776, pp. 207–216. Springer, Heidelberg (2000). https://doi.org/10.1007/10719839_21 CrossRef

Aumann, Y., Rabin, M.O.: Information theoretically secure communication in the limited storage space model. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 65–79. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48405-1_5

Babai, L., Gál, A., Kimmel, P.G., Lokam, S.V.: Communication complexity of simultaneous messages. SIAM J. Comput. 33(1), 137–166 (2004)CrossRefMATHMathSciNet

Babai, L., Hayes, T.P., Kimmel, P.G.: The cost of the missing bit: communication complexity with help. Combinatorica 21(4), 455–488 (2001)CrossRefMATHMathSciNet

Babai, L., Nisan, N., Szegedy, M.: Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs. J. Comput. Syst. Sci. 45(2), 204–232 (1992)CrossRefMATHMathSciNet

Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: Ashby, V. (ed.) ACM CCS 1993, Fairfax, Virginia, USA, pp. 62–73. ACM Press, 3–5 November 1993

Brands, S., Chaum, D.: Distance-bounding protocols. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 344–359. Springer, Heidelberg (1994). https://doi.org/10.1007/3-540-48285-7_30

Brassard, G.: Quantum information: the conundrum of secure positioning. Nature 479, 307–308 (2011)CrossRef

10.

Buhrman, H., Chandran, N., Fehr, S., Gelles, R., Goyal, V., Ostrovsky, R., Schaffner, C.: Position-based quantum cryptography: impossibility and constructions. SIAM J. Comput. 43(1), 150–178 (2014)CrossRefMATHMathSciNet

11.

Cachin, C., Maurer, U.: Unconditional security against memory-bounded adversaries. In: Kaliski, B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 292–306. Springer, Heidelberg (1997). https://doi.org/10.1007/BFb0052243 CrossRef

12.

Capkun, S., Hubaux, J.-P.: Secure positioning of wireless devices with application to sensor networks. In: Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies, INFOCOM 2005, vol. 3, pp. 1917–1928. IEEE, March 2005

13.

Cash, D., Ding, Y.Z., Dodis, Y., Lee, W., Lipton, R., Walfish, S.: Intrusion-resilient key exchange in the bounded retrieval model. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 479–498. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-70936-7_26 CrossRef

14.

Chakraborty, K., Leverrier, A.: Practical position-based quantum cryptography. Phys. Rev. A 92, 052304 (2015)CrossRef

15.

Chandra, A.K., Furst, M.L., Lipton, R.J.: Multi-party protocols. In: Proceedings of the 15th Annual ACM Symposium on the Theory of Computing, pp. 94–99 (1983)

16.

Chandran, N., Goyal, V., Moriarty, R., Ostrovsky, R.: Position-based cryptography. SIAM J. Comput. 43(4), 1291–1341 (2014)CrossRefMATHMathSciNet

17.

Dziembowski, S.: Intrusion-resilience via the bounded-storage model. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 207–224. Springer, Heidelberg (2006). https://doi.org/10.1007/11681878_11 CrossRef

18.

Dziembowski, S., Maurer, U.M.: Tight security proofs for the bounded-storage model. In: 34th ACM STOC, pp. 341–350, Montréal, Québec, Canada. ACM Press, 19–21 May 2002

19.

Dziembowski, S., Maurer, U.M.: Optimal randomizer efficiency in the bounded-storage model. J. Crypt. 17(1), 5–26 (2004)CrossRefMATHMathSciNet

20.

Dziembowski, S., Pietrzak, K.: Intrusion-resilient secret sharing. In 48th FOCS, Providence, USA, pp. 227–237. IEEE Computer Society Press, 20–23 October 2007

21.

Dziembowski, S., Zdanowicz, M.: Position-based cryptography from noisy channels. In: Pointcheval, D., Vergnaud, D. (eds.) AFRICACRYPT 2014. LNCS, vol. 8469, pp. 300–317. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-06734-6_19 CrossRef

22.

Ford, J., Gál, A.: Hadamard tensors and lower bounds on multiparty communication complexity. Comput. Complex. 22(3), 595–622 (2013)CrossRefMATHMathSciNet

23.

Graham, F.C.: Quasi-random hypergraphs revisited. Random Struct. Algorithms 40(1), 39–48 (2012)CrossRefMATHMathSciNet

24.

Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (1997)CrossRefMATH

25.

Lu, C.-J.: Encryption against storage-bounded adversaries from on-line strong extractors. J. Crypt. 17(1), 27–42 (2004)CrossRefMATHMathSciNet

26.

Maurer, U.M.: Conditionally-perfect secrecy and a provably-secure randomized cipher. J. Crypt. 5(1), 53–66 (1992)CrossRefMATHMathSciNet

27.

Moran, T., Shaltiel, R., Ta-Shma, A.: Non-interactive timestamping in the bounded-storage model. J. Crypt. 22(2), 189–226 (2009)CrossRefMATHMathSciNet

28.

Nisan, N., Wigderson, A.: Rounds in communication complexity revisited. In: 23rd ACM STOC, New Orleans, Louisiana, USA, pp. 419–429. ACM Press, 6–8 May 1991

29.

Nisan, N., Zuckerman, D.: Randomness is linear in space. J. Comput. Syst. Sci. 52(1), 43–52 (1996)CrossRefMATHMathSciNet

30.

Pudlák, P.: Unexpected upper bounds on the complexity of some communication games. In: Abiteboul, S., Shamir, E. (eds.) ICALP 1994. LNCS, vol. 820, pp. 1–10. Springer, Heidelberg (1994). https://doi.org/10.1007/3-540-58201-0_53 CrossRef

31.

Pudlk, P., Rödl, V., Sgall, J.: Boolean circuits, tensor ranks, and communication complexity. SIAM J. Comput. 26(3), 605–633 (1997)CrossRefMATHMathSciNet

32.

Raz, R.: The BNS-Chung criterion for multi-party communication complexity. Comput. Complex. 9(2), 113–122 (2000)CrossRefMATHMathSciNet

33.

Sastry, N., Shankar, U., Wagner, D.: Secure verification of location claims. In: Proceedings of the 2nd ACM Workshop on Wireless Security, WiSe 2003, pp. 1–10. ACM, New York (2003)

34.

Schaffner, C.: Position-based quantum cryptography. Webpage. http://homepages.cwi.nl/schaffne/positionbasedqcrypto.php. Accessed 17 Feb 2016

35.

Unruh, D.: Quantum position verification in the random oracle model. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8617, pp. 1–18. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44381-1_1 CrossRef

36.

Vadhan, S.P.: Constructing locally computable extractors and cryptosystems in the bounded-storage model. J. Crypt. 17(1), 43–77 (2004)CrossRefMATHMathSciNet

37.

Vora, A., Nesterenko, M.: Secure location verification using radio broadcast. In: Higashino, T. (ed.) OPODIS 2004. LNCS, vol. 3544, pp. 369–383. Springer, Heidelberg (2005). https://doi.org/10.1007/11516798_27 CrossRef

Titel: Position-Based Cryptography and Multiparty Communication Complexity
verfasst von: Joshua Brody
Stefan Dziembowski
Sebastian Faust
Krzysztof Pietrzak
Verlag: Springer International Publishing
Buch: Theory of Cryptography
Print ISBN: 978-3-319-70499-9

Electronic ISBN: 978-3-319-70500-2

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-70500-2_3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"