Cryptology ePrint Archive: Report 2016/536

Position-Based Cryptography and Multiparty Communication Complexity

Joshua Brody and Stefan Dziembowski and 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.

Category / Keywords: foundations /

Original Publication (in the same form): IACR-TCC-2017

Date: received 30 May 2016, last revised 26 Sep 2017

Contact author: stefan dziembowski at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20170926:101632 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]