Paper 2009/364

Position Based Cryptography

Nishanth Chandran, Vipul Goyal, Ryan Moriarty, and Rafail Ostrovsky

Abstract

We consider what constitutes {\em identities\/} in cryptography. Typical examples include your name and your social-security number, or your fingerprint/iris-scan, or your address, or your (non-revoked) public-key coming from some trusted public-key infrastructure. In many situations, however, {\bf where you are} defines your identity. For example, we know the role of a bank-teller behind a bullet-proof bank window not because she shows us her credentials but by merely knowing her location. In this paper, we initiate the study of cryptographic protocols where the identity (or other credentials and inputs) of a party are derived from its \emph{geographic location}. We start by considering the central task in this setting, i.e., securely verifying the position of a device. Despite much work in this area, we show that in the Vanilla (or standard) model, the above task (i.e., of secure positioning) is impossible to achieve. In light of the above impossibility result, we then turn to the Bounded Retrieval Model (a variant of the Bounded Storage Model) and formalize and construct information theoretically secure protocols for two fundamental tasks: \begin{itemize} \item Secure Positioning; and \item Position Based Key Exchange. \end{itemize} We then show that these tasks are in fact {\em universal\/} in this setting -- we show how we can use them to realize Secure Multi-Party Computation. Our main contribution in this paper is threefold: to place the problem of secure positioning on a sound theoretical footing; to prove a strong impossibility result that simultaneously shows the insecurity of previous attempts at the problem; and to present positive results by showing that the bounded-retrieval framework is, in fact, one of the ``right" frameworks (there may be others) to study the foundations of position-based cryptography.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Full version of paper to appear at CRYPTO'09
Keywords
secure positioningextractorsbounded retrieval model
Contact author(s)
nishanth @ cs ucla edu
History
2009-07-27: received
Short URL
https://ia.cr/2009/364
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/364,
      author = {Nishanth Chandran and Vipul Goyal and Ryan Moriarty and Rafail Ostrovsky},
      title = {Position Based Cryptography},
      howpublished = {Cryptology {ePrint} Archive, Paper 2009/364},
      year = {2009},
      url = {https://eprint.iacr.org/2009/364}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.