Paper 2024/830

How (not) to Build Quantum PKE in Minicrypt

Longcheng Li, State Key Lab of Processors, Institute of Computing Technology, Chinese Academy of Sciences.
Qian Li, Shenzhen International Center For Industrial And Applied Mathematics, Shenzhen Research Institute of Big Data
Xingjian Li, Tsinghua University
Qipeng Liu, University of California, San Diego
Abstract

The seminal work by Impagliazzo and Rudich (STOC'89) demonstrated the impossibility of constructing classical public key encryption (PKE) from one-way functions (OWF) in a black-box manner. However, the question remains: can quantum PKE (QPKE) be constructed from quantumly secure OWF? A recent line of work has shown that it is indeed possible to build QPKE from OWF, but with one caveat --- they rely on quantum public keys, which cannot be authenticated and reused. In this work, we re-examine the possibility of perfect complete QPKE in the quantum random oracle model (QROM), where OWF exists. Our first main result: QPKE with classical public keys, secret keys and ciphertext, does not exist in the QROM, if the key generation only makes classical queries. Therefore, a necessary condition for constructing such QPKE from OWF is to have the key generation classically ``un-simulatable’’. Previous discussions (Austrin~et al. CRYPTO'22) on the impossibility of QPKE from OWF rely on a seemingly strong conjecture. Our work makes a significant step towards a complete and unconditional quantization of Impagliazzo and Rudich’s results. Our second main result extends to QPKE with quantum public keys. The second main result: QPKE with quantum public keys, classical secret keys and ciphertext, does not exist in the QROM, if the key generation only makes classical queries and the quantum public key is either pure or ``efficiently clonable''. The result is tight due to all existing QPKEs constructions. Our result further gives evidence on why existing QPKEs lose reusability. To achieve these results, we use a novel argument based on conditional mutual information and quantum Markov chain by Fawzi and Renner (Communications in Mathematical Physics). We believe the techniques used in the work will find other usefulness in separations in quantum cryptography/complexity.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in CRYPTO 2024
Keywords
Key AgreementQuantum Random OracleMinicrypt
Contact author(s)
lilongcheng22s @ ict ac cn
liqian ict @ gmail com
lxj22 @ mails tsinghua edu cn
qipengliu0 @ gmail com
History
2024-05-31: approved
2024-05-28: received
See all versions
Short URL
https://ia.cr/2024/830
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/830,
      author = {Longcheng Li and Qian Li and Xingjian Li and Qipeng Liu},
      title = {How (not) to Build Quantum {PKE} in Minicrypt},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/830},
      year = {2024},
      url = {https://eprint.iacr.org/2024/830}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.