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.