{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:44:12Z","timestamp":1787341452755,"version":"build-2736575974"},"reference-count":52,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>In this paper, we initiate the theoretical study of cryptographic protocols where the identity, or other credentials and inputs, of a party are derived from its 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, even if we assume that the adversary is computationally bounded. In light of the above impossibility result, we then turn to Dziembowski's bounded retrieval model (a variant of Maurer's bounded storage model) and formalize and construct information theoretically secure protocols for two fundamental tasks: secure positioning and position-based key exchange. We then show that these tasks are in fact universal in this setting---we show how we can use them to realize secure multiparty 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 showing that the bounded-retrieval framework is a fruitful one to study the foundations of position-based cryptography.<\/jats:p>","DOI":"10.1137\/100805005","type":"journal-article","created":{"date-parts":[[2014,7,16]],"date-time":"2014-07-16T12:20:09Z","timestamp":1405513209000},"page":"1291-1341","source":"Crossref","is-referenced-by-count":10,"title":["Position-Based Cryptography"],"prefix":"10.1137","volume":"43","author":[{"given":"Nishanth","family":"Chandran","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vipul","family":"Goyal","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ryan","family":"Moriarty","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rafail","family":"Ostrovsky","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2014,7,16]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2002.1003845"},{"key":"atypb2","first-page":"65","author":"Aumann Y.","year":"1999","journal-title":"Proceedings of CRYPTO"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/0217014"},{"key":"atypb4","first-page":"1","author":"M.","year":"1988","journal-title":"Illinois"},{"key":"atypb5","first-page":"344","author":"Brands S.","year":"1994","journal-title":"New York"},{"key":"atypb6","first-page":"429","author":"Buhrman H.","year":"2011","journal-title":"Proceedings of CRYPTO"},{"key":"atypb7","unstructured":"L. Bussard,\n                      Trust Establishment Protocols for Communicating Devices\n                      , Ph.D. thesis, Eurecom-ENST, 2004."},{"key":"atypb8","first-page":"493","author":"Cachin C.","year":"1998","journal-title":"Proceedings of FOCS"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0052243"},{"key":"atypb10","first-page":"280","author":"Cagalj M.","year":"2006","journal-title":"Proceedings of IEEE Symposium on Security and Privacy"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"S. Capkun, M. Cagalj, and M. Srivastava,\n                      Secure localization with hidden and mobile base stations\n                      , in Proceedings of IEEE INFOCOM, 2006.","DOI":"10.1109\/INFOCOM.2006.302"},{"key":"atypb13","first-page":"1","author":"Capkun S.","year":"2006","journal-title":"Proceedings of Workshop on Wireless Security"},{"key":"atypb14","first-page":"1917","author":"Capkun S.","year":"2005","journal-title":"Proceedings of IEEE the INFOCOM"},{"key":"atypb15","first-page":"106","author":"Carter L.","year":"1977","journal-title":"Proceedings of STOC"},{"key":"atypb16","first-page":"479","author":"Cash D.","year":"2007","journal-title":"New York"},{"key":"atypb17","unstructured":"N. Chandran, S. Fehr, R. Gelles, V. Goyal, and R. Ostrovsky,\n                      Position-Based Quantum Cryptography\n                      , preprint, arXiv\/quant-ph:1005.1750, 2010."},{"key":"atypb18","first-page":"391","author":"Chandran N.","year":"2009","journal-title":"Proceedings of CRYPTO"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1145\/1514274.1514301"},{"key":"atypb20","first-page":"225","author":"Crescenzo G. Di","year":"2006","journal-title":"Proceedings of TCC"},{"key":"atypb21","first-page":"446","author":"Ding Y. Z.","year":"2004","journal-title":"Proceedings of TCC"},{"key":"atypb22","first-page":"1","author":"Ding Y. Z.","year":"2002","journal-title":"Proceedings of STACS"},{"key":"atypb23","first-page":"155","author":"Ding Y. Z.","year":"2001","journal-title":"Proceedings of CRYPTO"},{"key":"atypb24","first-page":"578","author":"Ding Y. Z.","year":"2005","journal-title":"Proceedings of TCC"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1029\/91RG00152"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795291562"},{"key":"atypb27","first-page":"126","author":"Dziembowski S.","year":"2004","journal-title":"Proceedings of EUROCRYPT"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-003-0309-y"},{"key":"atypb29","doi-asserted-by":"crossref","unstructured":"S. Dziembowski and K. Pietrzak,\n                      Intrusion-resilient secret sharing\n                      , in FOCS '07: Proceedings of the 48th Annual IEEE Foundations of Computer Science, 2007, pp. 227-237.","DOI":"10.1109\/FOCS.2007.63"},{"key":"atypb30","doi-asserted-by":"crossref","unstructured":"S. Dziembowski and K. Pietrzak,\n                      Leakage-resilient cryptography\n                      , in FOCS '08: Proceedings of the 49th Annual IEEE Foundations of Computer Science, 2008, pp. 293-302.","DOI":"10.1109\/FOCS.2008.56"},{"key":"atypb31","first-page":"207","author":"Dziembowski S.","year":"2006","journal-title":"Proceedings of TCC"},{"key":"atypb32","first-page":"251","author":"Dziembowski S.","year":"2006","journal-title":"New York"},{"key":"atypb33","first-page":"218","author":"Goldreich O.","year":"1987","journal-title":"Proceedings of STOC"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793244708"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.84.012326"},{"key":"atypb36","unstructured":"A. Kent, W. Munro, T. Spiller, and R. Beausoleil,\n                      Tagging Systems\n                      , U.S. patent 2006\/0022832, 2006."},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.83.012322"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-003-0217-1"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.81.042319"},{"key":"atypb40","first-page":"1","author":"Malaney R. A.","year":"2010","journal-title":"GLOBECOM"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1007\/BF00191321"},{"key":"atypb42","first-page":"460","author":"Moran T.","year":"2004","journal-title":"Proceedings of CRYPTO"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0004"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1137\/060671553"},{"key":"atypb45","first-page":"433","author":"Rackoff C.","year":"1991","journal-title":"Proceedings of CRYPTO"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1824"},{"key":"atypb47","doi-asserted-by":"crossref","unstructured":"N. Sastry, U. Shankar, and D. Wagner,\n                      Secure verification of location claims\n                      , in WiSe '03: Proceedings of the 2003 ACM Workshop on Wireless Security, 2003, pp. 1-10.","DOI":"10.1145\/941311.941313"},{"key":"atypb48","unstructured":"D. Singelee and B. Preneel,\n                      Location verification using secure distance bounding protocols\n                      , in Proceedings of the IEEE Conference on Mobile Adhoc and Sensor Systems, Washington, DC, 2005."},{"key":"atypb49","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502099"},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-003-0237-x"},{"key":"atypb51","doi-asserted-by":"crossref","unstructured":"A. Vora and M. Nesterenko,\n                      Secure location verification using radio broadcast\n                      , in Proceedings of OPODIS '04: 8th International Conference on Principles of Distributed Systems, 2004, pp. 369-383.","DOI":"10.1007\/11516798_27"},{"key":"atypb52","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2005.863855"},{"key":"atypb53","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199712)11:4<345::AID-RSA4>3.0.CO;2-Z"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/100805005","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:21:07Z","timestamp":1787340067000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/100805005"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":52,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1137\/100805005"],"URL":"https:\/\/doi.org\/10.1137\/100805005","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]}}}