Communications in Cryptology IACR CiC

Towards the Impossibility of Quantum Public Key Encryption with Classical Keys from One-Way Functions

Authors

Samuel Bouaziz–Ermann, Alex B. Grilo, Damien Vergnaud, Quoc-Huy Vu
Samuel Bouaziz–Ermann ORCID
Sorbonne Université, CNRS, LIP6, Paris, France
samuel dot bouaziz-ermann at lip6 dot fr
Alex B. Grilo ORCID
Sorbonne Université, CNRS, LIP6, Paris, France
alex dot bredariol-grilo at lip6 dot fr
Damien Vergnaud ORCID
Sorbonne Université, CNRS, LIP6, Paris, France
damien dot vergnaud at lip6 dot fr
Quoc-Huy Vu ORCID
Léonard de Vinci Pôle Universitaire, Research Center, Paris La Défense, France
quoc dot huy dot vu at ens dot fr

Abstract

There has been a recent interest in proposing quantum protocols whose security relies on weaker computational assumptions than their classical counterparts. Importantly to our work, it has been recently shown that public-key encryption (PKE) from one-way functions (OWF) is possible if we consider quantum public keys. Notice that we do not expect classical PKE from OWF given the impossibility results of Impagliazzo and Rudich (STOC'89).

However, the distribution of quantum public keys is a challenging task. Therefore, the main question that motivates our work is if quantum PKE from OWF is possible if we have classical public keys. Such protocols are impossible if ciphertexts are also classical, given the impossibility result of Austrin et al.(CRYPTO'22) of quantum enhanced key-agreement (KA) with classical communication.

In this paper, we focus on black-box separation for PKE with classical public key and quantum ciphertext from OWF under the polynomial compatibility conjecture, first introduced in Austrin et al.. More precisely, we show the separation when the decryption algorithm of the PKE does not query the OWF. We prove our result by extending the techniques of Austrin et al. and we show an attack for KA in an extended classical communication model where the last message in the protocol can be a quantum state.

References

[ACC+22]
Per Austrin, Hao Chung, Kai-Min Chung, Shiuan Fu, Yao-Ting Lin, and Mohammad Mahmoody. On the impossibility of key agreements from quantum random oracles. In Yevgeniy Dodis and Thomas Shrimpton, editors, CRYPTO 2022, Part II, volume 13508 of LNCS, 165–194. August 2022. Springer, Heidelberg. https://doi.org/10.1007/978-3-031-15979-4_6.
Google Scholar ePrint
[AQY22]
Prabhanjan Ananth, Luowen Qian, and Henry Yuen. Cryptography from pseudorandom quantum states. In Yevgeniy Dodis and Thomas Shrimpton, editors, CRYPTO 2022, Part I, volume 13507 of LNCS, 208–236. August 2022. Springer, Heidelberg. https://doi.org/10.1007/978-3-031-15802-5_8.
Google Scholar ePrint
[BB84]
Charles H. Bennett and Gilles Brassard. Quantum cryptography: public key distribution and coin tossing. In IEEE International Conference on Computers, Systems and Signal Processing, volume 175, 8. 1984. https://doi.org/https://doi.org/10.1016/j.tcs.2014.05.025.
Google Scholar ePrint
[BCKM21]
James Bartusek, Andrea Coladangelo, Dakshita Khurana, and Fermi Ma. On the round complexity of secure quantum computation. In Tal Malkin and Chris Peikert, editors, CRYPTO 2021, Part I, volume 12825 of LNCS, 406–435. Virtual Event, August 2021. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-84242-0_15.
Google Scholar ePrint
[BGHD+23]
Khashayar Barooti, Alex B. Grilo, Loïs Huguenin-Dumittan, Giulio Malavolta, Or Sattath, Quoc-Huy Vu, and Michael Walter. Public-key encryption with quantum keys. In Guy Rothblum and Hoeteck Wee, editors, Theory of Cryptography, 198–227. Cham, 2023. Springer Nature Switzerland. https://doi.org/10.1007/978-3-031-48624-1_8.
Google Scholar ePrint
[BM09]
Boaz Barak and Mohammad Mahmoody-Ghidary. Merkle puzzles are optimal - an $O(n^2)$-query attack on any key exchange from a random oracle. In Shai Halevi, editor, CRYPTO 2009, volume 5677 of LNCS, 374–390. August 2009. Springer, Heidelberg. https://doi.org/10.1007/978-3-642-03356-8_22.
Google Scholar ePrint
[CLM23]
Kai-Min Chung, Yao-Ting Lin, and Mohammad Mahmoody. Black-box separations for non-interactive classical commitments in a quantum world. In Carmit Hazay and Martijn Stam, editors, EUROCRYPT 2023, Part I, volume 14004 of LNCS, 144–172. April 2023. Springer, Heidelberg. https://doi.org/10.1007/978-3-031-30545-0_6.
Google Scholar ePrint
[Col23]
Andrea Coladangelo. Quantum trapdoor functions from classical one-way functions. CoRR, 2023. https://doi.org/10.48550/arXiv.2302.12821.
Google Scholar ePrint
[GLSV21]
Alex B. Grilo, Huijia Lin, Fang Song, and Vinod Vaikuntanathan. Oblivious transfer is in MiniQCrypt. In Anne Canteaut and François-Xavier Standaert, editors, EUROCRYPT 2021, Part II, volume 12697 of LNCS, 531–561. October 2021. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-77886-6_18.
Google Scholar ePrint
[IR89]
Russell Impagliazzo and Steven Rudich. Limits on the provable consequences of one-way permutations. In 21st ACM STOC, 44–61. May 1989. ACM Press. https://doi.org/10.1145/73007.73012.
Google Scholar ePrint
[KMNY23]
Fuyuki Kitagawa, Tomoyuki Morimae, Ryo Nishimaki, and Takashi Yamakawa. Quantum public-key encryption with tamper-resilient public keys from one-way functions. 2023. https://doi.org/10.48550/arXiv.2304.01800.
Google Scholar ePrint
[KQST23]
William Kretschmer, Luowen Qian, Makrand Sinha, and Avishay Tal. Quantum cryptography in algorithmica. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, 1589–1602. New York, NY, USA, 2023. Association for Computing Machinery. https://doi.org/10.1145/3564246.3585225.
Google Scholar ePrint
[Kre21]
William Kretschmer. Quantum pseudorandomness and classical complexity. In Min-Hsiu Hsieh, editor, 16th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2021, July 5-8, 2021, Virtual Conference, volume 197 of LIPIcs, 2:1–2:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.TQC.2021.2.
Google Scholar ePrint
[MY22]
Tomoyuki Morimae and Takashi Yamakawa. One-wayness in quantum cryptography. 2022. https://doi.org/10.48550/arXiv.2210.03394.
Google Scholar ePrint
[NC10]
Michael A Nielsen and Isaac L Chuang. Quantum computation and quantum information. Cambridge university press, 2010. https://doi.org/https://doi.org/10.1017/CBO9780511976667.
Google Scholar ePrint
[Wie83]
Stephen Wiesner. Conjugate coding. SIGACT News, 15(1):78–88, 1983. https://doi.org/10.1145/1008908.1008920.
Google Scholar ePrint
[Zha19]
Mark Zhandry. How to record quantum queries, and applications to quantum indifferentiability. In Alexandra Boldyreva and Daniele Micciancio, editors, CRYPTO 2019, Part II, volume 11693 of LNCS, 239–268. August 2019. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-26951-7_9.
Google Scholar ePrint

PDFPDF Open access

DOI: https://doi.org/10.62056/ahvr-11zn4
History
Submitted: 2024-01-09
Accepted: 2024-03-05
Published: 2024-04-09
How to cite

Samuel Bouaziz–Ermann, Alex B. Grilo, Damien Vergnaud, and Quoc-Huy Vu, "Towards the Impossibility of Quantum Public Key Encryption with Classical Keys from One-Way Functions," IACR Communications in Cryptology, vol. 1, no. 1, Apr 09, 2024, doi: 10.62056/ahvr-11zn4.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.