TL;DR
This paper proves that it's impossible to construct perfect quantum public-key encryption (QPKE) schemes from quantumly secure one-way functions (OWFs) using a black-box approach. This impossibility is linked to a new conjecture about low-degree polynomials on the Boolean hypercube, and the authors provide evidence and prove special cases of this conjecture.
What Problem Does This Paper Address?
Public-key encryption (PKE) is a cornerstone of modern cryptography, enabling secure communication over insecure channels. While classical PKE has been extensively studied, the advent of quantum computing has raised questions about the security of these schemes and the assumptions needed to build them. Specifically, researchers are interested in constructing quantum public-key encryption (QPKE) schemes that are secure against quantum adversaries, and understanding what fundamental cryptographic primitives are sufficient for their construction.
Previous work has shown that constructing PKE from one-way functions (OWFs) in a black-box manner is impossible. However, the situation for QPKE is more nuanced. While some QPKE schemes can be built from OWFs, these often involve quantum keys or ciphertexts, which can be cumbersome. The open question is whether QPKE with classical public keys, secret keys, and ciphertexts can be constructed solely from quantumly secure OWFs in a black-box model. This paper tackles this question by showing that such a construction is impossible, provided a new conjecture about polynomials on the Boolean hypercube holds.
Methods
The core of the paper's contribution lies in connecting the impossibility of constructing QPKE from OWFs to a new conjecture about low-degree polynomials on the Boolean hypercube. The authors introduce Conjecture 1, which states that for any non-constant low-degree polynomial, there's a randomized way to modify a small number of input bits such that the polynomial evaluated on the modified input avoids zero with high probability.
Assuming this conjecture, the authors employ an information-theoretical approach, similar to recent work by Li, Li, Li, and Liu (CRYPTO'24), to demonstrate the impossibility of black-box QPKE constructions from OWFs. They also explore various pieces of evidence supporting their conjecture and prove several special cases.
Key techniques include:
- Boolean Function Analysis (BFA): The paper heavily relies on tools and concepts from BFA, particularly the Fourier expansion of functions on the hypercube and the analysis of polynomial degrees.
- Information-Theoretic Approach: The proof of impossibility leverages information-theoretic arguments to show that certain cryptographic tasks are inherently difficult to achieve under the given assumptions.
- Conjecture Formulation: The introduction of Conjecture 1 is a central methodological contribution, providing a concrete mathematical problem whose resolution directly impacts the possibility of QPKE construction.
- Special Case Analysis: The authors analyze specific scenarios, such as when the key generation algorithm makes only classical or a logarithmic number of quantum queries, to provide concrete results and build evidence for their main conjecture.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- The Polynomial Conjecture is Key: The paper establishes a surprising and fundamental link between the feasibility of constructing quantum public-key encryption and the behavior of low-degree polynomials on the Boolean hypercube. This connection provides a new avenue for understanding the limits of cryptographic constructions.
- Black-Box Impossibility: The main result is a black-box separation: it's impossible to build perfect QPKE from quantum OWFs using standard black-box proof techniques, if their polynomial conjecture holds. This means that any proof of such a construction would have to go beyond the typical black-box paradigm.
- Conjecture 1 as a Central Hypothesis: The paper proposes Conjecture 1 as a crucial hypothesis. Its strength lies in its apparent simplicity and its connection to existing notions in BFA, making it a promising target for further research.
- QPKE is Harder Than We Thought (from OWFs): The results suggest that achieving perfect QPKE from basic quantum primitives like OWFs is significantly more challenging than initially hoped, especially in a black-box setting.
- Progress on Specific Cases: The paper makes concrete progress by ruling out QPKE from OWFs when the key generation algorithm has limited quantum query complexity (e.g., logarithmic queries), improving upon prior results.
Key Results
- Main Theorem: Assuming Conjecture 1 is true, perfect complete QPKE cannot be constructed from quantumly secure OWFs in a black-box manner.
- Conjecture 1: A novel conjecture about low-degree polynomials on the Boolean hypercube is proposed and supported with evidence.
- Special Case 1 (Gen makes classical queries): Perfect complete QPKE does not exist in the QROM if the key generation algorithm only makes classical queries. This improves upon previous work.
- Special Case 3 (Gen makes O(log n) quantum queries): Perfect complete QPKE does not exist in the QROM if the key generation algorithm makes only O(log n) quantum queries.
- Special Case 4 (Gen has "uniform" outputs): Perfect complete QPKE does not exist in the QROM if the key generation algorithm has "uniform" outputs.
- Evidence from Combinatorial Nullstellensatz: The paper shows that a weaker version of Conjecture 1, implied by the Combinatorial Nullstellensatz, already leads to non-existence results for certain QPKE schemes.
Limitations and Future Work
- Reliance on Conjecture 1: The main result's validity hinges on the truth of Conjecture 1. While the paper provides evidence and proves special cases, a full proof of the conjecture itself remains an open problem. The authors suggest that further research into BFA and related areas might resolve this conjecture.
- Black-Box Model: The impossibility result is specifically for black-box constructions. It does not preclude the possibility of constructing QPKE from OWFs using non-black-box techniques, though such constructions are generally harder to prove secure.
- "Perfect" QPKE: The results focus on "perfect" QPKE, meaning schemes with zero error probability. Future work could explore the implications for "computational" QPKE, which allows for negligible error.
- Exploring Conjecture 1 Further: The paper calls for more research into Conjecture 1 and its equivalent forms, particularly investigating the constant 'c' in Conjecture 8 and exploring its implications for other cryptographic primitives.
- Non-Black-Box Constructions: Investigating whether QPKE can be constructed from OWFs using non-black-box techniques remains an open and challenging direction.
Summary updated