You are looking at a specific version 20220107:165317 of this paper. See the latest version.

Paper 2022/008

Beating Classical Impossibility of Position Verification

Jiahui Liu and Qipeng Liu and Luowen Qian

Abstract

Chandran et al. (SIAM J. Comput.'14) formally introduced the cryptographic task of position verification, where they also showed that it cannot be achieved by classical protocols. In this work, we initiate the study of position verification protocols with classical verifiers. We identify that proofs of quantumness (and thus computational assumptions) are necessary for such position verification protocols. For the other direction, we adapt the proof of quantumness protocol by Brakerski et al. (FOCS'18) to instantiate such a position verification protocol. As a result, we achieve classically verifiable position verification assuming the quantum hardness of Learning with Errors. Along the way, we develop the notion of 1-of-2 non-local soundness for a natural non-local game for 1-of-2 puzzles, first introduced by Radian and Sattath (AFT'19), which can be viewed as a computational unclonability property. We show that 1-of-2 non-local soundness follows from the standard 2-of-2 soundness (and therefore the adaptive hardcore bit property), which could be of independent interest.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. ITCS 2022
Keywords
cryptographic protocolposition verificationquantum cryptographyproof of quantumnessnon-locality
Contact author(s)
jiahui @ cs utexas edu,qipengliu0 @ gmail com,luowenq @ bu edu
History
2022-01-07: received
Short URL
https://ia.cr/2022/008
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.