Paper 2016/536

Position-Based Cryptography and Multiparty Communication Complexity

Joshua Brody, Stefan Dziembowski, Sebastian Faust, and Krzysztof Pietrzak

Abstract

\emph{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 \emph{secure positioning} and \emph{position-based key agreement} in the \emph{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 \emph{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 \emph{locality} requirement in the bounded-storage model to \emph{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 \emph{negative} results in one area (in our case: lower bounds in multiparty communication complexity) can be used to construct secure cryptographic schemes.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published by the IACR in TCC 2017
Contact author(s)
stefan dziembowski @ gmail com
History
2017-09-26: revised
2016-05-31: received
See all versions
Short URL
https://ia.cr/2016/536
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/536,
      author = {Joshua Brody and Stefan Dziembowski and Sebastian Faust and Krzysztof Pietrzak},
      title = {Position-Based Cryptography and Multiparty Communication Complexity},
      howpublished = {Cryptology ePrint Archive, Paper 2016/536},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/536}},
      url = {https://eprint.iacr.org/2016/536}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.