Document Open Access Logo

Proofs of Quantumness from Trapdoor Permutations

Authors Tomoyuki Morimae, Takashi Yamakawa

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.87.pdf
  • Filesize: 0.68 MB
  • 14 pages

Document Identifiers

Author Details

Tomoyuki Morimae
  • Yukawa Institute for Theoretical Physics, Kyoto University, Japan
Takashi Yamakawa
  • NTT Social Informatics Laboratories, Tokyo, Japan
  • Yukawa Institute for Theoretical Physics, Kyoto University, Japan

Funding

  • Morimae, Tomoyuki: JST Moonshot JPMJMS2061-5-1-1, JST FOREST, MEXT QLEAP, the Grant-in-Aid for Scientific Research (B) No.JP19H04066, the Grant-in Aid for Transformative Research Areas (A) 21H05183, and the Grant-in-Aid for Scientific Research (A) No.22H00522.

Cite AsGet BibTex

Tomoyuki Morimae and Takashi Yamakawa. Proofs of Quantumness from Trapdoor Permutations. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 87:1-87:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ITCS.2023.87

Abstract

Assume that Alice can do only classical probabilistic polynomial-time computing while Bob can do quantum polynomial-time computing. Alice and Bob communicate over only classical channels, and finally Bob gets a state |x₀⟩+|x₁⟩ with some bit strings x₀ and x₁. Is it possible that Alice can know {x₀,x₁} but Bob cannot? Such a task, called remote state preparations, is indeed possible under some complexity assumptions, and is bases of many quantum cryptographic primitives such as proofs of quantumness, (classical-client) blind quantum computing, (classical) verifications of quantum computing, and quantum money. A typical technique to realize remote state preparations is to use 2-to-1 trapdoor collision resistant hash functions: Alice sends a 2-to-1 trapdoor collision resistant hash function f to Bob, and Bob evaluates it coherently, i.e., Bob generates ∑_x|x⟩|f(x)⟩. Bob measures the second register to get the measurement result y, and sends y to Alice. Bob’s post-measurement state is |x₀⟩+|x₁⟩, where f(x₀) = f(x₁) = y. With the trapdoor, Alice can learn {x₀,x₁} from y, but due to the collision resistance, Bob cannot. This Alice’s advantage can be leveraged to realize the quantum cryptographic primitives listed above. It seems that the collision resistance is essential here. In this paper, surprisingly, we show that the collision resistance is not necessary for a restricted case: we show that (non-verifiable) remote state preparations of |x₀⟩+|x₁⟩ secure against classical probabilistic polynomial-time Bob can be constructed from classically-secure (full-domain) trapdoor permutations. Trapdoor permutations are not likely to imply the collision resistance, because black-box reductions from collision-resistant hash functions to trapdoor permutations are known to be impossible. As an application of our result, we construct proofs of quantumness from classically-secure (full-domain) trapdoor permutations.

Subject Classification

ACM Subject Classification
  • Theory of computation → Cryptographic primitives
Keywords
  • Quantum cryptography
  • Proofs of quantumness
  • Trapdoor permutations

Metrics

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

References

  1. Ryan Amos, Marios Georgiou, Aggelos Kiayias, and Mark Zhandry. One-shot signatures and applications to hybrid quantum/classical authentication. In 52nd ACM STOC, pages 255-268. ACM Press, 2020. URL: https://doi.org/10.1145/3357713.3384304.
  2. László Babai, Robert Beals, and Ákos Seress. Polynomial-time theory of matrix groups. In Michael Mitzenmacher, editor, 41st ACM STOC, pages 55-64. ACM Press, May / June 2009. URL: https://doi.org/10.1145/1536414.1536425.
  3. Christian Badertscher, Alexandru Cojocaru, Léo Colisson, Elham Kashefi, Dominik Leichtle, Atul Mantri, and Petros Wallden. Security limitations of classical-client delegated quantum computing. In ASIACRYPT 2020, Part II, LNCS, pages 667-696. Springer, Heidelberg, December 2020. URL: https://doi.org/10.1007/978-3-030-64834-3_23.
  4. Mihir Bellare and Silvio Micali. How to sign given any trapdoor permutation. J. ACM, 39(1):214-233, 1992. Google Scholar
  5. Nir Bitansky, Omer Paneth, and Daniel Wichs. Perfect structure on the edge of chaos - trapdoor permutations from indistinguishability obfuscation. In Eyal Kushilevitz and Tal Malkin, editors, TCC 2016-A, Part I, volume 9562 of LNCS, pages 474-502. Springer, Heidelberg, January 2016. URL: https://doi.org/10.1007/978-3-662-49096-9_20.
  6. Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh Vazirani, and Thomas Vidick. A cryptographic test of quantumness and certifiable randomness from a single quantum device. Journal of the ACM, 68(5):31:1-31:47, 2021. Google Scholar
  7. Zvika Brakerski, Paul 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 FOCS, pages 320-331. IEEE Computer Society Press, October 2018. URL: https://doi.org/10.1109/FOCS.2018.00038.
  8. Zvika Brakerski, Venkata Koppula, Umesh Vazirani, and Thomas Vidick. Simpler proofs of quantumness. In Steven T. Flammia, editor, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2020, June 9-12, 2020, Riga, Latvia, volume 158 of LIPIcs, pages 8:1-8:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.TQC.2020.4.
  9. Anne Broadbent, Joseph Fitzsimons, and Elham Kashefi. Universal blind quantum computation. In 50th FOCS, pages 517-526. IEEE Computer Society Press, October 2009. URL: https://doi.org/10.1109/FOCS.2009.36.
  10. Alexandru Cojocaru, Léo Colisson, Elham Kashefi, and Petros Wallden. QFactory: Classically-instructed remote secret qubits preparation. In Steven D. Galbraith and Shiho Moriai, editors, ASIACRYPT 2019, Part I, volume 11921 of LNCS, pages 615-645. Springer, Heidelberg, December 2019. URL: https://doi.org/10.1007/978-3-030-34578-5_22.
  11. Vedran Dunjko and Elham Kashefi. Blind quantum computing with two almost identical states. arXiv:1604.01586, 2016. Google Scholar
  12. Shimon Even, Oded Goldreich, and Abraham Lempel. A randomized protocol for signing contracts. Communications of the ACM, 28(6):637-647, 1985. Google Scholar
  13. Uriel Feige, Dror Lapidot, and Adi Shamir. Multiple noninteractive zero knowledge proofs under general assumptions. SIAM J. Comput., 29(1):1-28, 1999. Google Scholar
  14. Sanjam Garg and Mohammad Hajiabadi. Trapdoor functions from the computational Diffie-Hellman assumption. In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part II, volume 10992 of LNCS, pages 362-391. Springer, Heidelberg, August 2018. URL: https://doi.org/10.1007/978-3-319-96881-0_13.
  15. Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In Richard E. Ladner and Cynthia Dwork, editors, 40th ACM STOC, pages 197-206. ACM Press, May 2008. URL: https://doi.org/10.1145/1374376.1374407.
  16. Alexandru Gheorghiu, Tony Metger, and Alexander Poremba. Quantum cryptography with classical communication: parallel remote state preparation for copy-protection, verification, and more. arXiv:2201.13445, 2022. Google Scholar
  17. Alexandru Gheorghiu and Thomas Vidick. Computationally-secure and composable remote state preparation. In David Zuckerman, editor, 60th FOCS, pages 1024-1033. IEEE Computer Society Press, November 2019. URL: https://doi.org/10.1109/FOCS.2019.00066.
  18. Oded Goldreich and Leonid A Levin. A hard-core predicate for all one-way functions. In STOC, pages 25-32. ACM, 1989. Google Scholar
  19. Oded Goldreich and Ron D. Rothblum. Enhancements of trapdoor permutations. Journal of Cryptology, 26(3):484-512, July 2013. URL: https://doi.org/10.1007/s00145-012-9131-8.
  20. Iftach Haitner, Jonathan J. Hoch, Omer Reingold, and Gil Segev. Finding collisions in interactive protocols - tight lower bounds on the round and communication complexities of statistically hiding commitments. SIAM J. Comput., 44(1):193-242, 2015. URL: https://doi.org/10.1137/130938438.
  21. Iftach Haitner, Omer Horvitz, Jonathan Katz, Chiu-Yuen Koo, Ruggero Morselli, and Ronen Shaltiel. Reducing complexity assumptions for statistically-hiding commitment. In Ronald Cramer, editor, EUROCRYPT 2005, volume 3494 of LNCS, pages 58-77. Springer, Heidelberg, May 2005. URL: https://doi.org/10.1007/11426639_4.
  22. Iftach Haitner, Minh-Huyen Nguyen, Shien Jin Ong, Omer Reingold, and Salil P. Vadhan. Statistically hiding commitments and statistical zero-knowledge arguments from any one-way function. SIAM J. Comput., 39(3):1153-1218, 2009. Google Scholar
  23. Sean Hallgren. Polynomial-time quantum algorithms for Pell’s equation and the principal ideal problem. In 34th ACM STOC, pages 653-658. ACM Press, May 2002. URL: https://doi.org/10.1145/509907.510001.
  24. Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. NTRU: A ring-based public key cryptosystem. In Joe Buhler, editor, Algorithmic Number Theory, Third International Symposium, ANTS-III, Portland, Oregon, USA, June 21-25, 1998, Proceedings, volume 1423 of Lecture Notes in Computer Science, pages 267-288. Springer, 1998. Google Scholar
  25. Akinori Hosoyamada and Takashi Yamakawa. Finding collisions in a quantum world: Quantum black-box separation of collision-resistance and one-wayness. In ASIACRYPT 2020, Part I, LNCS, pages 3-32. Springer, Heidelberg, December 2020. URL: https://doi.org/10.1007/978-3-030-64837-4_1.
  26. Yuval Ishai, Eyal Kushilevitz, and Rafail Ostrovsky. Sufficient conditions for collision-resistant hashing. In Joe Kilian, editor, TCC 2005, volume 3378 of LNCS, pages 445-456. Springer, Heidelberg, February 2005. URL: https://doi.org/10.1007/978-3-540-30576-7_24.
  27. Gregory D. Kahanamoku-Meyer, Soonwon Choi, Umesh V. Vazirani, and Norman Y. Yao. Classically verifiable quantum advantage from a computational bell test. Nature Physics, 2022. Google Scholar
  28. Yael Tauman Kalai, Alex Lombardi, Vinod Vaikuntanathan, and Lisa Yang. Quantum advantage from any non-local game. Cryptology ePrint Archive, Paper 2022/400, 2022. URL: https://eprint.iacr.org/2022/400.
  29. Urmila Mahadev. Classical homomorphic encryption for quantum circuits. In Mikkel Thorup, editor, 59th FOCS, pages 332-338. IEEE Computer Society Press, October 2018. URL: https://doi.org/10.1109/FOCS.2018.00039.
  30. Urmila Mahadev. Classical verification of quantum computations. In Mikkel Thorup, editor, 59th FOCS, pages 259-267. IEEE Computer Society Press, October 2018. URL: https://doi.org/10.1109/FOCS.2018.00033.
  31. Robert J. McEliece. . a public key cryptosystem based on algebraic coding theory. DSN progress report, 1978. Google Scholar
  32. Moni Naor, Rafail Ostrovsky, Ramarathnam Venkatesan, and Moti Yung. Perfect zero-knowledge arguments for NP can be based on general complexity assumptions (extended abstract). In Ernest F. Brickell, editor, CRYPTO'92, volume 740 of LNCS, pages 196-214. Springer, Heidelberg, August 1993. URL: https://doi.org/10.1007/3-540-48071-4_14.
  33. Harald Niederreiter. Knapsack-type cryptosystems and algebraic coding theory. Prob. Contr. Inform. Theory, 15(2):157-166, 1986. Google Scholar
  34. Chris Peikert and Brent Waters. Lossy trapdoor functions and their applications. In Richard E. Ladner and Cynthia Dwork, editors, 40th ACM STOC, pages 187-196. ACM Press, May 2008. URL: https://doi.org/10.1145/1374376.1374406.
  35. Roy Radian and Or Sattath. Semi-quantum money. arXiv, abs/1908.08889, 2019. URL: http://arxiv.org/abs/1908.08889.
  36. Omri Shmueli. Public-key quantum money with a classical bank. Cryptology ePrint Archive, Paper 2021/1427, 2021. URL: https://eprint.iacr.org/2021/1427.
  37. Omri Shmueli. Semi-quantum tokenized signatures. Cryptology ePrint Archive, Paper 2022/228, 2022. URL: https://eprint.iacr.org/2022/228.
  38. Peter W. Shor. Algorithms for quantum computation: Discrete logarithms and factoring. In 35th FOCS, pages 124-134. IEEE Computer Society Press, November 1994. URL: https://doi.org/10.1109/SFCS.1994.365700.
  39. Takashi Yamakawa and Mark Zhandry. Verifiable quantum advantage without structure. Cryptology ePrint Archive, Paper 2022/434, 2022. URL: https://eprint.iacr.org/2022/434.
  40. Jiayu Zhang. Classical verification of quantum computations in linear time. Cryptology ePrint Archive, Paper 2022/432, 2022. URL: https://eprint.iacr.org/2022/432.
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 Imprint Privacy Contact