---
res:
bibo_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.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Joshua
foaf_name: Brody, Joshua
foaf_surname: Brody
- foaf_Person:
foaf_givenName: Stefan
foaf_name: Dziembowski, Stefan
foaf_surname: Dziembowski
- foaf_Person:
foaf_givenName: Sebastian
foaf_name: Faust, Sebastian
foaf_surname: Faust
- foaf_Person:
foaf_givenName: Krzysztof Z
foaf_name: Pietrzak, Krzysztof Z
foaf_surname: Pietrzak
foaf_workInfoHomepage: http://www.librecat.org/personId=3E04A7AA-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-9139-1654
bibo_doi: 10.1007/978-3-319-70500-2_3
bibo_volume: 10677
dct_date: 2017^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/978-331970499-9
dct_language: eng
dct_publisher: Springer@
dct_title: Position based cryptography and multiparty communication complexity@
...