Full quantum one‐way function for quantum cryptography

Luowen Qian

Mohamed Ahmed Shalaby

Tao Shang, Yao Tang, Ranyiliu Chen +1 more

One-way functions are fundamental tools for cryptography. Until now, quantum one-way functions have several input-output categories such as “classical-to-classical,” “classical-to-quantum,” and “quantum-to-classical,” which are used for postquantum cryptography or quantum cryptography. However, there are still no intrinsic “quantum-to-quantum” quantum one-way functions. In this article, we propose the full quantum one-way function to design full quantum cryptographic schemes. By concatenating the “quantum-classical” one-way function and the rotation operation of single qubit, the full quantum one-way function has the input and output of quantum states. We prove its one-way property from “easy computation” and “computationally difficult to invert.” Then we apply the full quantum one-way function to quantum identity authentication. Security analysis shows that the proposed quantum identity authentication scheme based on the full quantum one-way function is secure even under active attacks.

Boyang Chen, Tomoyuki Morimae, Takashi Yamakawa

Pessiland is a world where NP is hard on average but one-way functions (OWFs) do not exist [Impagliazzo 1995]. Because almost all classical cryptographic primitives imply OWFs [Impagliazzo and Luby 1989], there is almost no classical cryptography in Pessiland. On the other hand, quantum cryptography can exist even when OWFs do not [Kretschmer 2021; Morimae and Yamakawa 2022; Ananth, Qian and Yuen 2022]. Is there a quantum analogue of Pessiland where NP is hard on average but even quantum cryptography does not exist? In this paper, we show that such a miserable world, Quantum Pessiland, exists: there is a quantum oracle relative to which $UP\cap coUP$ is hard on average against quantum polynomial-time algorithms with quantum advice, yet auxiliary-input EFI pairs do not exist. We also show that there is a classical oracle relative to which $UP\cap coUP$ is hard on average against quantum polynomial-time algorithms with quantum advice, yet classically-secure auxiliary-input one-way puzzles (OWPuzzs) do not exist. Almost all quantum cryptographic primitives imply EFI pairs or OWPuzzs, and therefore these results mean that there is almost no quantum cryptography relative to these oracles. We further show that relative to the classical oracle, SampBQP = SampBPP, and therefore there is no sampling-based quantum advantage in Quantum Pessiland. Finally, because our average-case hardness of $UP\cap coUP$ implies $P^{\#P}\not\subseteq i.o.BQP/qpoly$, our result also implies that a non-relativizing proof technique is necessary to construct OWPuzzs solely from $P^{\#P}\not\subseteq i.o.BQP/qpoly$, which gives a partial negative answer to the open problem of [Khurana and Tomer 2025].

Tao Shang, Yao Tang, Jianwei Liu

Quantum one-way function (QOWF) was proposed for quantum cryptography, which was computable but almost irreversible in quantum polynomial time. Full quantum one-way function (F-QOWF) is one of the most important models of QOWF, which deals with quantum states. Although the universal construction of full quantum one-way function has been proposed, there is still little further discussion on the entangled input, specific function instantiation and application scenarios of F-QOWF. In this paper, we introduce quantum hypergraph states into the universal construction of F-QOWF. Quantum hypergraph states are highly entangled multi-party states constructed from the hypergraph. By applying quantum hypergraph states to the new F-QOWF, we generalize the universal construction of F-QOWF to entangled states. The application to quantum aggregate signature shows that quantum hypergraph states help the new F-QOWF be well applied to quantum multi-party cryptographic protocols.

Sam Buxbaum, Mohammad Mahmoody

In classical cryptography, one-way functions (OWFs) play a central role as the minimal primitive that (almost) all primitives imply. The situation is more complicated in quantum cryptography, in which honest parties and adversaries can use quantum computation and communication, and it is known that analogues of OWFs in the quantum setting might not be minimal. In this work we ask whether OWFs are minimal for the intermediate setting of post-quantum cryptography, in which the protocols are classical while they shall resist quantum adversaries. We show that for a wide range of natural settings, if a primitive Q implies OWFs, then so does its (uniformly or non-uniformly secure) post-quantum analogue. In particular, we show that if a primitive Q implies any other primitive P that has a 2-message security game (e.g., OWFs) through a black-box classical security reduction R, then one can always (efficiently) turn any polynomial-size quantum adversary breaking P into a polynomial-size quantum adversary breaking Q. Note that this result holds even if the implementation of P using that of Q is arbitrarily non-black-box. We also prove extensions of this result for when the reduction R anticipates its oracle adversary to be deterministic, whenever either of the following conditions hold: (1) the adversary needs to win the security game of Q only with non-negligible probability (e.g., Q is collision-resistant hashing) or (2) that either of P and Q have “falsifiable” security games (this is the case when P is OWFs). Our work leaves open answering our main question when Q implies OWFs through a non-black-box security reduction, or when P uses a more complicated security game than a two-message one.