Document Open Access Logo

Beating Classical Impossibility of Position Verification

Authors Jiahui Liu, Qipeng Liu, Luowen Qian

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.100.pdf
  • Filesize: 0.54 MB
  • 11 pages

Document Identifiers

Author Details

Jiahui Liu
  • Department of Computer Science, University of Texas at Austin, TX, USA
Qipeng Liu
  • Simons Institute for the Theory of Computing, Berkeley, CA, USA
Luowen Qian
  • Department of Computer Science, Boston University, MA, USA

Funding

  • Liu, Jiahui: supported by the NSF and Scott Aaronson’s Simons Investigator award.
  • Liu, Qipeng: supported by the Simons Institute for the Theory of Computing, through a Quantum Postdoctoral Fellowship.
  • Qian, Luowen: supported by DARPA under Agreement No. HR00112020023.

Acknowledgements

The authors would like to thank Ran Canetti and Shih-Han Hung for their helpful discussions.

Cite As Get BibTex

Jiahui Liu, Qipeng Liu, and Luowen Qian. Beating Classical Impossibility of Position Verification. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 100:1-100:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ITCS.2022.100

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Cryptographic protocols
  • Security and privacy → Authorization
  • Security and privacy → Public key (asymmetric) techniques
  • Theory of computation → Quantum query complexity
  • Theory of computation → Quantum complexity theory
Keywords
  • cryptographic protocol
  • position verification
  • quantum cryptography
  • proof of quantumness
  • non-locality

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Scott Aaronson. Limitations of quantum advice and one-way communication. Theory Comput., 1(1):1-28, 2005. URL: https://doi.org/10.4086/toc.2005.v001a001.
  2. Scott Aaronson. Quantum computing, postselection, and probabilistic polynomial-time. Proceedings: Mathematical, Physical and Engineering Sciences, 461(2063):3473-3482, 2005. URL: http://www.jstor.org/stable/30047928.
  3. Gorjan Alagic, Andrew M. Childs, Alex B. Grilo, and Shih-Han Hung. Non-interactive classical verification of quantum computation. In Rafael Pass and Krzysztof Pietrzak, editors, Theory of Cryptography - 18th International Conference, TCC 2020, Durham, NC, USA, November 16-19, 2020, Proceedings, Part III, volume 12552 of Lecture Notes in Computer Science, pages 153-180. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-64381-2_6.
  4. Gorjan Alagic, Tommaso Gagliardoni, and Christian Majenz. Can you sign a quantum state?, 2021. URL: http://arxiv.org/abs/1811.11858v3.
  5. Rene Allerstorfer, Harry Buhrman, Florian Speelman, and Philip Verduyn Lunel. New protocols and ideas for practical quantum position verification, 2021. URL: http://arxiv.org/abs/2106.12911v1.
  6. Howard Barnum, Claude Crépeau, Daniel Gottesman, Adam D. Smith, and Alain Tapp. Authentication of quantum messages. In 43rd Symposium on Foundations of Computer Science (FOCS 2002), 16-19 November 2002, Vancouver, BC, Canada, Proceedings, pages 449-458. IEEE Computer Society, 2002. URL: https://doi.org/10.1109/SFCS.2002.1181969.
  7. Salman Beigi and Robert König. Simplified instantaneous non-local quantum computation with applications to position-based cryptography. New Journal of Physics, 13(9):093036, September 2011. URL: https://doi.org/10.1088/1367-2630/13/9/093036.
  8. Andreas Bluhm, Matthias Christandl, and Florian Speelman. Position-based cryptography: Single-qubit protocol secure against multi-qubit attacks, 2021. URL: http://arxiv.org/abs/2104.06301v2.
  9. Dan Boneh, Özgür Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner, and Mark Zhandry. Random oracles in a quantum world. In Dong Hoon Lee and Xiaoyun Wang, editors, Advances in Cryptology - ASIACRYPT 2011 - 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, December 4-8, 2011. Proceedings, volume 7073 of Lecture Notes in Computer Science, pages 41-69. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-25385-0_3.
  10. Zvika Brakerski, Paul F. Christiano, Urmila Mahadev, Umesh V. Vazirani, and Thomas Vidick. A cryptographic test of quantumness and certifiable randomness from a single quantum device. In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 320-331. IEEE Computer Society, 2018. URL: https://doi.org/10.1109/FOCS.2018.00038.
  11. Joshua Brody, Stefan Dziembowski, Sebastian Faust, and Krzysztof Pietrzak. Position-based cryptography and multiparty communication complexity. In Yael Kalai and Leonid Reyzin, editors, Theory of Cryptography - 15th International Conference, TCC 2017, Baltimore, MD, USA, November 12-15, 2017, Proceedings, Part I, volume 10677 of Lecture Notes in Computer Science, pages 56-81. Springer, 2017. URL: https://doi.org/10.1007/978-3-319-70500-2_3.
  12. Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, and Christian Schaffner. Position-based quantum cryptography: Impossibility and constructions. SIAM J. Comput., 43(1):150-178, 2014. URL: https://doi.org/10.1137/130913687.
  13. Harry Buhrman, Serge Fehr, Christian Schaffner, and Florian Speelman. The garden-hose model. In Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, ITCS '13, pages 145-158, New York, NY, USA, 2013. Association for Computing Machinery. URL: https://doi.org/10.1145/2422436.2422455.
  14. Ran Canetti, Shai Halevi, and Michael Steiner. Hardness amplification of weakly verifiable puzzles. In Joe Kilian, editor, Theory of Cryptography, Second Theory of Cryptography Conference, TCC 2005, Cambridge, MA, USA, February 10-12, 2005, Proceedings, volume 3378 of Lecture Notes in Computer Science, pages 17-33. Springer, 2005. URL: https://doi.org/10.1007/978-3-540-30576-7_2.
  15. Nishanth Chandran, Vipul Goyal, Ryan Moriarty, and Rafail Ostrovsky. Position-based cryptography. SIAM J. Comput., 43(4):1291-1341, 2014. URL: https://doi.org/10.1137/100805005.
  16. Nai-Hui Chia, Kai-Min Chung, and Takashi Yamakawa. Classical verification of quantum computations with efficient verifier. In Rafael Pass and Krzysztof Pietrzak, editors, Theory of Cryptography - 18th International Conference, TCC 2020, Durham, NC, USA, November 16-19, 2020, Proceedings, Part III, volume 12552 of Lecture Notes in Computer Science, pages 181-206. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-64381-2_7.
  17. Siddhartha Das and George Siopsis. Practically secure quantum position verification. New Journal of Physics, 23(6):063069, June 2021. URL: https://doi.org/10.1088/1367-2630/ac0755.
  18. Marius Junge, Aleksander M. Kubicki, Carlos Palazuelos, and David Pérez-García. Geometry of banach spaces: a new route towards position based cryptography, 2021. URL: http://arxiv.org/abs/2103.16357v2.
  19. Adrian Kent, William J. Munro, and Timothy P. Spiller. Quantum tagging: Authenticating location via quantum information and relativistic signaling constraints. Phys. Rev. A, 84:012326, 2011. URL: https://doi.org/10.1103/PhysRevA.84.012326.
  20. Fuyuki Kitagawa, Ryo Nishimaki, and Takashi Yamakawa. Secure software leasing from standard assumptions, 2021. URL: http://arxiv.org/abs/2010.11186v3.
  21. Bing Qi and George Siopsis. Loss-tolerant position-based quantum cryptography. Phys. Rev. A, 91:042337, April 2015. URL: https://doi.org/10.1103/PhysRevA.91.042337.
  22. Roy Radian and Or Sattath. Semi-quantum money. In Proceedings of the 1st ACM Conference on Advances in Financial Technologies, AFT 2019, Zurich, Switzerland, October 21-23, 2019, pages 132-146. ACM, 2019. URL: https://doi.org/10.1145/3318041.3355462.
  23. Tobias Schmitt-Manderbach, Henning Weier, Martin Fürst, Rupert Ursin, Felix Tiefenbacher, Thomas Scheidl, Josep Perdigues, Zoran Sodnik, Christian Kurtsiefer, John G. Rarity, Anton Zeilinger, and Harald Weinfurter. Experimental demonstration of free-space decoy-state quantum key distribution over 144 km. Phys. Rev. Lett., 98:010504, January 2007. URL: https://doi.org/10.1103/PhysRevLett.98.010504.
  24. Marco Tomamichel, Serge Fehr, Jędrzej Kaniewski, and Stephanie Wehner. A monogamy-of-entanglement game with applications to device-independent quantum cryptography. New Journal of Physics, 15(10):103002, 2013. URL: https://doi.org/10.1088/1367-2630/15/10/103002.
  25. Dominique Unruh. Quantum position verification in the random oracle model. In Juan A. Garay and Rosario Gennaro, editors, Advances in Cryptology - CRYPTO 2014, pages 1-18, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg. Google Scholar
  26. R. Ursin, F. Tiefenbacher, T. Schmitt-Manderbach, H. Weier, T. Scheidl, M. Lindenthal, B. Blauensteiner, T. Jennewein, J. Perdigues, P. Trojek, and et al. Entanglement-based quantum communication over 144 km. Nature Physics, 3(7):481-486, June 2007. URL: https://doi.org/10.1038/nphys629.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact