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.
翻译:Chandran 等人(SIAM J.compuut.''14) 正式引入定位核查的加密任务, 其中它们也表明它无法通过古典协议实现。 在这项工作中,我们开始与古典验证人研究定位核查协议。 我们确认量度证明(因而是计算假设)对于这种定位核查协议是必要的。 在另一个方向上,我们调整Brakerski等人(FOCS'18)的量度证明协议,以即刻执行这种位置核查协议。 因此,我们取得了典型的可核查位置核查,假设学习与错误的量度硬度。 沿途,我们为1比2的自然非本地游戏开发了1比2的非本地声音的概念, 最初由Radian和Satth(AFT'19)提出, 这可以被视为计算不可计算的财产。 我们显示, 1比2的非本地声音符合标准2的稳度(因此是适应的硬点位), 这可能是独立感兴趣的。