Document Open Access Logo

Depth-Bounded Quantum Cryptography with Applications to One-Time Memory and More

Author Qipeng Liu

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.82.pdf
  • Filesize: 0.7 MB
  • 18 pages

Document Identifiers

Author Details

Qipeng Liu
  • Simons Institute for the Theory of Computing, Berkeley, CA, USA

Funding

  • Liu, Qipeng: supported in part by the Simons Institute for the Theory of Computing, through a Quantum Postdoctoral Fellowship and by the DARPA sieve-vespa grant HR00112020023.

Acknowledgements

The authors would like to thank Shafi Goldwasser for so many insightful discussions. Without whom, this work would be impossible.

Cite As Get BibTex

Qipeng Liu. Depth-Bounded Quantum Cryptography with Applications to One-Time Memory and More. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 82:1-82:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ITCS.2023.82

Abstract

With the power of quantum information, we can achieve exciting and classically impossible cryptographic primitives. However, almost all quantum cryptography faces extreme difficulties with the near-term intermediate-scale quantum technology (NISQ technology); namely, the short lifespan of quantum states and limited sequential computation. At the same time, considering only limited quantum adversaries may still enable us to achieve never-before-possible tasks.
In this work, we consider quantum cryptographic primitives against limited quantum adversaries - depth-bounded adversaries. We introduce a model for (depth-bounded) NISQ computers, which are classical circuits interleaved with shallow quantum circuits. Then, we show one-time memory can be achieved against any depth-bounded quantum adversaries introduced in the work, with their depth being any pre-fixed polynomial. Therefore we obtain applications like one-time programs and one-time proofs. Finally, we show our one-time memory has correctness even against constant-rate errors.

Subject Classification

ACM Subject Classification
  • Theory of computation → Cryptographic protocols
  • Security and privacy → Authorization
  • Security and privacy → Public key (asymmetric) techniques
Keywords
  • cryptographic protocol
  • one-time memory
  • quantum cryptography

Metrics

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

References

  1. Scott Aaronson. Quantum copy-protection and quantum money. In 2009 24th Annual IEEE Conference on Computational Complexity, pages 229-242. IEEE, 2009. Google Scholar
  2. Scott Aaronson and Paul Christiano. Quantum money from hidden subspaces. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 41-60, 2012. Google Scholar
  3. Scott Aaronson, Jiahui Liu, Qipeng Liu, Mark Zhandry, and Ruizhe Zhang. New approaches for quantum copy-protection. In Annual International Cryptology Conference, pages 526-555. Springer, 2021. Google Scholar
  4. Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, and Umesh Vazirani. Dense quantum coding and quantum finite automata. Journal of the ACM (JACM), 49(4):496-511, 2002. Google Scholar
  5. Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, et al. Quantum supremacy using a programmable superconducting processor. Nature, 574(7779):505-510, 2019. Google Scholar
  6. Boaz Barak, Oded Goldreich, Rusell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, and Ke Yang. On the (im) possibility of obfuscating programs. In Annual international cryptology conference, pages 1-18. Springer, 2001. Google Scholar
  7. James Bartusek and Dakshita Khurana. Cryptography with certified deletion. arXiv preprint, 2022. URL: http://arxiv.org/abs/2207.01754.
  8. Amit Behera, Or Sattath, and Uriel Shinar. Noise-tolerant quantum tokens for mac. arXiv preprint, 2021. URL: http://arxiv.org/abs/2105.05016.
  9. Mihir Bellare and Phillip Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In Proceedings of the 1st ACM Conference on Computer and Communications Security, pages 62-73, 1993. Google Scholar
  10. Charles H Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and weaknesses of quantum computing. SIAM journal on Computing, 26(5):1510-1523, 1997. Google Scholar
  11. Charles H Bennett and Gilles Brassard. Quantum cryptography: Public key distribution and coin tossing. arXiv preprint, 2020. URL: http://arxiv.org/abs/2003.06557.
  12. Nir Bitansky, Shafi Goldwasser, Abhishek Jain, Omer Paneth, Vinod Vaikuntanathan, and Brent Waters. Time-lock puzzles from randomized encodings. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pages 345-356, 2016. Google Scholar
  13. Jeremiah Blocki, Seunghoon Lee, and Samson Zhou. On the security of proofs of sequential work in a post-quantum world. arXiv preprint, 2020. URL: http://arxiv.org/abs/2006.10972.
  14. 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.
  15. Anne Broadbent, Sevag Gharibian, and Hong-Sheng Zhou. Towards quantum one-time memories from stateless hardware. Quantum, 5:429, 2021. Google Scholar
  16. Anne Broadbent and Rabib Islam. Quantum encryption with certified deletion. In Theory of Cryptography Conference, pages 92-122. Springer, 2020. Google Scholar
  17. Anne Broadbent and Sébastien Lord. Uncloneable quantum encryption via oracles. arXiv preprint, 2019. URL: http://arxiv.org/abs/1903.00130.
  18. Ran Canetti. Universally composable security: A new paradigm for cryptographic protocols. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 136-145. IEEE, 2001. Google Scholar
  19. Michael Capalbo, Omer Reingold, Salil Vadhan, and Avi Wigderson. Randomness conductors and constant-degree lossless expanders. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 659-668, 2002. Google Scholar
  20. Nai-Hui Chia, Kai-Min Chung, and Ching-Yi Lai. On the need for large quantum depth. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 902-915, 2020. Google Scholar
  21. Nai-Hui Chia and Shih-Han Hung. Classical verification of quantum depth. arXiv preprint, 2022. URL: http://arxiv.org/abs/2205.04656.
  22. Kai-Min Chung, Serge Fehr, Yu-Hsuan Huang, and Tai-Ning Liao. On the compressed-oracle technique, and post-quantum security of proofs of sequential work. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 598-629. Springer, 2021. Google Scholar
  23. Kai-Min Chung, Marios Georgiou, Ching-Yi Lai, and Vassilis Zikas. Cryptography with disposable backdoors. Cryptography, 3(3):22, 2019. Google Scholar
  24. Andrea Coladangelo, Jiahui Liu, Qipeng Liu, and Mark Zhandry. Hidden cosets and applications to unclonable cryptography. In Annual International Cryptology Conference, pages 556-584. Springer, 2021. Google Scholar
  25. Matthew Coudron and Sanketh Menda. Computations with greater quantum depth are strictly more powerful (relative to an oracle). In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 889-901, 2020. Google Scholar
  26. Eric Culf and Thomas Vidick. A monogamy-of-entanglement game for subspace coset states. arXiv preprint, 2021. URL: http://arxiv.org/abs/2107.13324.
  27. Akshay Degwekar, Vinod Vaikuntanathan, and Prashant Nalini Vasudevan. Fine-grained cryptography. In Annual International Cryptology Conference, pages 533-562. Springer, 2016. Google Scholar
  28. Shohei Egashira, Yuyu Wang, and Keisuke Tanaka. Fine-grained cryptography revisited. Journal of Cryptology, 34(3):1-43, 2021. Google Scholar
  29. Shafi Goldwasser, Dan Gutfreund, Alexander Healy, Tali Kaufman, and Guy N Rothblum. Verifying and decoding in constant depth. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 440-449, 2007. Google Scholar
  30. Shafi Goldwasser, Dan Gutfreund, Alexander Healy, Tali Kaufman, and Guy N Rothblum. A (de) constructive approach to program checking. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 143-152, 2008. Google Scholar
  31. Shafi Goldwasser, Yael Tauman Kalai, and Guy N Rothblum. One-time programs. In Annual International Cryptology Conference, pages 39-56. Springer, 2008. Google Scholar
  32. Johan Hastad. One-way permutations in nc0. Information Processing Letters, 26(3):153-155, 1987. Google Scholar
  33. IBM. Ibm announces advances to ibm quantum systems & ecosystem, 2017. URL: https://newsroom.ibm.com/2017-11-10-IBM-Announces-Advances-to-IBM-Quantum-Systems-Ecosystem.
  34. Jørn Justesen. Class of constructive asymptotically good algebraic codes. IEEE Transactions on Information Theory, 18(5):652-656, 1972. Google Scholar
  35. Gil Kalai. The argument against quantum computers. In Quantum, Probability, Logic, pages 399-422. Springer, 2020. Google Scholar
  36. Yehuda Lindell. How to simulate it-a tutorial on the simulation proof technique. Tutorials on the Foundations of Cryptography, pages 277-346, 2017. Google Scholar
  37. Cristopher Moore and Martin Nilsson. Parallel quantum computation and quantum codes. SIAM journal on computing, 31(3):799-815, 2001. Google Scholar
  38. Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2010. URL: https://doi.org/10.1017/CBO9780511976667.
  39. John Preskill. Quantum computing in the nisq era and beyond. Quantum, 2:79, 2018. Google Scholar
  40. R. L. Rivest, A. Shamir, and D. A. Wagner. Time-lock puzzles and timed-release crypto. Technical report, Massachusetts Institute of Technology, USA, 1996. Google Scholar
  41. Michael Sipser and Daniel A Spielman. Expander codes. IEEE transactions on Information Theory, 42(6):1710-1722, 1996. Google Scholar
  42. Barbara M Terhal and David P DiVincenzo. Adaptive quantum computation, constant depth quantum circuits and arthur-merlin games. arXiv preprint, 2002. URL: http://arxiv.org/abs/quant-ph/0205133.
  43. 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.
  44. Dominique Unruh. Universally composable quantum multi-party computation. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 486-505. Springer, 2010. Google Scholar
  45. Dominique Unruh. Revocable quantum timed-release encryption. J. ACM, 62(6), December 2015. URL: https://doi.org/10.1145/2817206.
  46. Hoeteck Wee. Zero knowledge in the random oracle model, revisited. In International Conference on the Theory and Application of Cryptology and Information Security, pages 417-434. Springer, 2009. Google Scholar
  47. Stephen Wiesner. Conjugate coding. ACM Sigact News, 15(1):78-88, 1983. Google Scholar
  48. Andrew Chi-Chih Yao. How to generate and exchange secrets. In 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), pages 162-167. IEEE, 1986. Google Scholar
  49. Mark Zhandry. Quantum lightning never strikes the same state twice. or: quantum money from cryptographic assumptions. Journal of Cryptology, 34(1):1-56, 2021. Google Scholar
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