Toward the Impossibility of Perfect Complete Quantum PKE from OWFs

Longcheng Li, Qian Li, Xingjian Li, Qipeng LiuITCS 2025 · OpenReview

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

Abstract

In this paper, we study the impossibility of constructing perfect complete quantum public key encryption (QPKE) from quantumly secure one-way functions (OWFs) in a black-box manner. We show that this problem is connected to a fundamental conjecture about the roots of low-degree polynomials on the Boolean hypercube. Informally, the conjecture asserts that for every nonconstant low-degree polynomial, there exists a universal (randomized) way to modify a small number of input bits such that, for every input string, the polynomial evaluated on the modified input string avoids 0 with sufficiently large probability (over the choice of how the input string is modified). Assuming this conjecture, we demonstrate the impossibility of constructing QPKE from quantumly secure one-way functions in a black-box manner, by employing the information-theoretical approach recently developed by Li, Li, Li, and Liu (CRYPTO'24). Towards resolving this conjecture, we provide various pieces of evidence supporting it and prove some special cases. In particular, we fully rule out perfect QPKE from OWFs when the key generation algorithm only makes a logarithmic number of quantum queries, improving the previous work, which can only handle classical queries.
BibTeX
@inproceedings{li2025toward,
  author = {Longcheng Li and Qian Li and Xingjian Li and Qipeng Liu},
  title = {{Toward the Impossibility of Perfect Complete Quantum PKE from OWFs}},
  booktitle = {ITCS},
  year = {2025},
  url = {https://openreview.net/forum?id=XINCfmaGv4},
}
Figure