تقرير
Beating Classical Impossibility of Position Verification
| العنوان: | Beating Classical Impossibility of Position Verification |
|---|---|
| المؤلفون: | Liu, Jiahui, Liu, Qipeng, Qian, Luowen |
| سنة النشر: | 2021 |
| المجموعة: | Computer Science Quantum Physics |
| مصطلحات موضوعية: | Quantum Physics, Computer Science - Cryptography and Security |
| الوصف: | 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. Comment: 33 pages, 1 figure, to be published in ITCS 2022. Expanded discussions on the usage of quantum memory. Fixed discussions in the introduction regarding ABSL21, BCS21, and extending the non-local game. Fixed typos |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2109.07517 |
| رقم الأكسشن: | edsarx.2109.07517 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |