Cryptomania v.s. Minicrypt in a Quantum World
Longcheng Li, Qian Li, Xingjian Li, Qipeng Liu · 2025
Read Cryptomania v.s. Minicrypt in a Quantum World by Longcheng Li, Qian Li, Xingjian Li, Qipeng Liu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-05710.txt.
Introduction
One-way functions are the minimum fuel of cryptography, and a long-standing question asks whether they suffice to build quantum public-key encryption with ordinary classical keys. Longcheng Li, Qian Li, Xingjian Li, and Qipeng Liu answer no, at least for black-box constructions. Working in the quantum random oracle model, they prove that no perfectly complete scheme of that kind can be secure.
The impossibility holds whether ciphertexts are classical or quantum. It also extends, in natural settings, to schemes whose public keys are quantum, which covers every known construction of that type. Earlier results needed unproven assumptions or limits on how keys may be generated. The proof redraws the map of what quantum cryptography must assume.
Catalog record
| CREATOR | Longcheng Li, Qian Li, Xingjian Li, Qipeng Liu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 72 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-05710
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Cryptomania v.s. Minicrypt in a Quantum World Longcheng Li, Qian Li, Xingjian Li, Qipeng Liu Abstract We prove that it is impossible to construct perfect-complete quantum public-key encryption (QPKE) with classical keys from quantumly secure one-way functions (OWFs) in a black-box manner, resolving a long-standing open question in quantum cryptography. Specifically, in the quantum random oracle model (QROM), no perfect-complete QPKE scheme with classical keys, and classical/quantum ciphertext can be secure. This improves the previous works which require either unproven conjectures or imposed restrictions on key generation algorithms. This impossibility extends to QPKE with quantum public key in natural settings, which is tight to all known QPKE constructions with quantum public key. 1 Introduction Quantum information and computation are topics with growing importance in cryptography. They reshape people’s views on cryptography drastically, including breaking classical secure cryptosystems [ 28 ] , creating primitives that are impossible for classical [ 29 ] , and weakening assumptions [ 9 ] . However, quantum cryptography is not an all-powerful tool, as it also has its own limits. Therefore, characterizing the boundary of quantum cryptography under different assumptions has become a topic of great interest. Boundaries between classical cryptographic primitives have already been studied extensively. In the seminal work by Impagliazzo and Rudich [ 18 ] , they proposed the methodology of black-box separation. They showed that one-way functions are insufficient to build public key encryption (PKE) schemes in a black-box manner. In the famous work by Impagliazzo [ 17 ] , he characterized five possibilities on the hardness of NP problems and their complexity consequences. Among them, he used the word ‘Minicrypt’ to refer to a world where one-way functions exist, and the word ‘Cryptomania’ for a world with public key cryptography primitives. Thus, the separation result by Impagliazzo and Rudich can be viewed as a separation between Minicrypt and Cryptomania. It turns out that the landscape of quantum cryptography varies depending on the definition of Minicrypt. For example, it is known that with quantum communication, many primitives in classical Cryptomania can be built from one-way functions, including key agreement [ 9 ] , oblivious transfer [ 15 , 7 ] , public key encryption (with quantum public keys) [ 12 , 25 , 19 , 6 ] . On the other hand, none of these constructions are known in the quantum computation classical communication (QCCC) setting. Quantum communication has various drawbacks in practice, including the difficulties of authenticating, broadcasting, reusability, and potentially adding interactions. In this work, we focus on the fundamental question regarding Minicrypt and Cryptomania in a quantum world [ 16 ] : Does there exist any separation between Minicrypt and Cryptomania in the QCCC setting? Previous works. Several works have attempted to address this question, but classical proof techniques often fail due to fundamental differences between quantum and classical algorithms/information, including challenges related to cloning, rewinding, and the unique structure of quantum queries. As a result, all previous approaches have either relied on unproven conjectures or applied only to highly restricted QPKE schemes. In the work by Austrin et al. [ 5 ] , they initialized the study of separations between quantum key agreements and one-way functions in the quantum random oracle model (QROM). They showed that under some conjecture named ‘polynomial compatibility conjecture’ , quantum key agreements with perfect correctness don’t exist. Since quantum PKE implies a two-round key agreement scheme, their result also implies a separation between quantum PKE and one-way functions. The same idea was also applied in separating PKE with quantum ciphertext and one-way functions [ 11 ] , which we will discuss later. To show a separation between key agreement and one-way function in the QROM, one needs to construct an eavesdropper that breaks the security of the key agreement by making polynomially many queries to the oracle. In the paper [ 5 ] , the authors construct an eavesdropper who only makes classical queries to the oracle, while Alice and Bob can make quantum queries in general. Because honest parties get quantum queries and the eavesdropper only classical queries, the conjecture may be too strong. In another line of work, Li, Li, Li, and Liu [ 21 ] approach the problem from a different perspective. They introduce tools from quantum Markov chains [ 13 ] to construct an eavesdropper for quantum public key encryption schemes that have a classical key generation process . On a high level, they construct an Eve who uses a polynomial number of quantum queries and creates a simulated view for Alice called \mathsf{A}^{\prime} , denoting the view of Alice before she tries to decrypt a ciphertext using the random oracle. Using the quantum Markov chain, they can argue that the state over the real Alice and Bob \mathsf{A}\mathsf{B} is statistically close to that over the simulated Alice and Bob \mathsf{A}^{\prime}\mathsf{B} . Finally, they finish running the simulated Alice with one caveat: the simulated Alice may not be consistent with the real random oracle, and they have to find an appropriate oracle to complete the execution. The work [ 21 ] solves this issue by only focusing on the key generation algorithm which makes only classical queries. In a followup paper [ 22 ] , the authors introduce a view from boolean function analysis as an attempt to attack PKE with quantum-query key generation. They made some conjecture about the zero point distributions of low-degree polynomials and proved that the conjecture implies a separation between perfect-complete PKE and OWF in the QCCC model. Both works fail to establish the separation once the key-generation algorithm is allowed to quantumly query a random oracle. More broadly, lifting separations proved in the classical-accessible-oracle model to the quantum-accessible-oracle model can be notoriously difficult. While several landmark separations are known with classically accessible oracles — e.g., quantum money v.s. one-way functions [ 3 ] and QCMA v.s. QMA [ 23 , 24 ] — whether these separations persist when the oracle admits quantum queries still remains a major open problem in quantum complexity and quantum cryptography; either these separation results completely fail when quantum access is provided, or they have to rely on unproven conjectures. 1.1 Our Main Result In this work, we refine the separation framework of [ 21 , 22 ] and present a unified approach to proving lower bounds and separations for multiparty-computation related primitives in the QROM. We hope the improved framework can be used for achieving lower bounds for other MPC related protocols with prefect completeness. Using that, we obtain a full separation between perfectly complete quantum PKE and one-way functions, i.e. the quantum version of [ 18 ] for public-key encryption, closing the gap in previous works. Theorem 1.1 (Informal) . Perfect-complete quantum public key encryption, with classical keys and classical ciphertext, does not exist in the quantum random oracle model. Remark 1.2 . Our result removes the conjecture used in [ 5 , 22 ] and the restriction of a classical key generation algorithm in [ 21 ] , leaving perfect completeness as the only requirement. Perfect completeness is a natural requirement satisfied by many cryptographic schemes, both classical and quantum, including all known quantum PKE schemes even with quantum keys [ 12 , 25 , 19