Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Quantum Engineering

Full quantum one‐way function for quantum cryptography

Tao Shang, Yao Tang, Ranyiliu Chen, Jianwei Liu

Published Feb 21, 2020• 31 citations
Publisher

Abstract

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.

DOI
10.1002/que2.32

Related papers

The existence of quantum one-way functions

Ping Wang, Yian Lei, Zishen Shen +1 more

One-way functions are essential tools for cryptography. However, the existence of one-way functions is still an open conjecture. By constructing a function with classical bits as input and quantum states as output, we prove the existence of quantum one-way functions more rigorously. It provides theoretical guarantees for the security of many quantum cryptographic protocols.

Modern Physics Letters A•May 8, 2025•0 citations

Full Quantum One-way Function Based on Quantum Hypergraph State

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.

International Conference on Wireless Communications and Signal Processing (WCSP)•Nov 2, 2023•2 citations

Quantum trapdoor functions from classical one-way functions

Andrea Coladangelo

We formalize and study the notion of a quantum trapdoor function. This is an efficiently computable unitary that takes as input a "public" quantum state and a classical string $x$, and outputs a quantum state. This map is such that (i) it is hard to invert, in the sense that it is hard to recover $x$ given the output state (and many copies of the public state), and (ii) there is a classical trapdoor that allows efficient inversion. We show that a quantum trapdoor function can be constructed from any quantum-secure one-way function. A direct consequence of this result is that, assuming just the existence of quantum-secure one-way functions, there exists a public-key encryption scheme with a (pure) quantum public key.

arXiv:2302.12821•Feb 24, 2023•4 citations

A Note on Quantum Security for Post-Quantum Cryptography.

Fang Song

Shor’s quantum factoring algorithm and a few other efficient quantum algorithms break many clas-sical crypto-systems. In response, people proposed post-quantum cryptography based on computational problems that are believed hard even for quantum computers. However, security of these schemes against quantum attacks is elusive. This is because existing security analysis (almost) only deals with classical attackers and arguing security in the presence of quantum adversaries is challenging due to unique quan-tum features such as no-cloning. This work proposes a general framework to study which classical security proofs can be restored in the quantum setting. Basically, we split a security proof into (a sequence of) classical security reductions, and investigate what security reductions are “quantum-friendly”. We characterize sufficient conditions such that a classical reduction can be “lifted ” to the quantum setting. We then apply our lifting theorems to post-quantum signature schemes. We are able to show that the classical generic construction of hash-tree based signatures from one-way functions and and a more efficient variant proposed in [BDH11] carry over to the quantum setting. Namely, assuming existence of (classical) one-way functions that are resistant to efficient quantum inversion algorithms, there exists a quantum-secure signature scheme. We note that the scheme in [BDH11] is a promising (post-quantum) candidate to be implemented in practice and our result further justifies it. Actually, to obtain these results, we formalize a simple criteria, which is motivated by many classical proofs in the literature and is straightforward to check. This makes our lifting theorem easier to apply, and it should be useful elsewhere to prove quantum security of proposed post-quantum cryptographic schemes. Finally we demonstrate the generality of our framework by showing that several existing works (Full-Domain hash in the quantum random-oracle model [Zha12b] and the simple hybrid arguments framework in [HSS11]) can be reformulated under our unified framework. 1

•Jan 1, 2014•0 citations

Generalized one-way function and its application

Hua‐Lei Yin

One-way functions are fundamental to classical cryptography and their existence remains a longstanding problem in computational complexity theory. Recently, a provable quantum one-way function has been identified, which maintains its one-wayness even with unlimited computational resources. Here, we extend the mathematical definition of functions to construct a generalized one-way function by virtually measuring the qubit of provable quantum one-way function and randomly assigning the corresponding measurement outcomes with identical probability. Remarkably, using this generalized one-way function, we have developed an unconditionally secure key distribution protocol based solely on classical data processing, which can then utilized for secure encryption and signature. Our work highlights the importance of information in characterizing quantum systems and the physical significance of the density matrix. We demonstrate that probability theory and randomness are effective tools for countering adversaries with unlimited computational capabilities.

arXiv:2408.13613•Aug 24, 2024•0 citations

One-Wayness in Quantum Cryptography

Tomoyuki Morimae, Takashi Yamakawa

The existence of one-way functions is one of the most fundamental assumptions in classical cryptography. In the quantum world, on the other hand, there are evidences that some cryptographic primitives can exist even if one-way functions do not exist. We therefore have the following important open problem in quantum cryptography: What is the most fundamental element in quantum cryptography? In this direction, Brakerski, Canetti, and Qian recently defined a notion called EFI pairs, which are pairs of efficiently generatable states that are statistically distinguishable but computationally indistinguishable, and showed its equivalence with some cryptographic primitives including commitments, oblivious transfer, and general multi-party computations. However, their work focuses on decision-type primitives and does not cover search-type primitives like quantum money and digital signatures. In this paper, we study properties of one-way state generators (OWSGs), which are a quantum analogue of one-way functions. We first revisit the definition of OWSGs and generalize it by allowing mixed output states. Then we show the following results. (1) We define a weaker version of OWSGs, weak OWSGs, and show that they are equivalent to OWSGs. (2) Quantum digital signatures are equivalent to OWSGs. (3) Private-key quantum money schemes (with pure money states) imply OWSGs. (4) Quantum pseudo one-time pad schemes imply both OWSGs and EFI pairs. (5) We introduce an incomparable variant of OWSGs, which we call secretly-verifiable and statistically-invertible OWSGs, and show that they are equivalent to EFI pairs.

arXiv:2210.03394•Leibniz international proceedings in informatics•Oct 7, 2022•13 citations
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.
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.
We formalize and study the notion of a quantum trapdoor function. This is an efficiently computable unitary that takes as input a "public" quantum state and a classical string xxx, and outputs a quantum state. This map is such that (i) it is hard to invert, in the sense that it is hard to recover xxx given the output state (and many copies of the public state), and (ii) there is a classical trapdoor that allows efficient inversion. We show that a quantum trapdoor function can be constructed from any quantum-secure one-way function. A direct consequence of this result is that, assuming just the existence of quantum-secure one-way functions, there exists a public-key encryption scheme with a (pure) quantum public key.
Shor’s quantum factoring algorithm and a few other efficient quantum algorithms break many clas-sical crypto-systems. In response, people proposed post-quantum cryptography based on computational problems that are believed hard even for quantum computers. However, security of these schemes against quantum attacks is elusive. This is because existing security analysis (almost) only deals with classical attackers and arguing security in the presence of quantum adversaries is challenging due to unique quan-tum features such as no-cloning. This work proposes a general framework to study which classical security proofs can be restored in the quantum setting. Basically, we split a security proof into (a sequence of) classical security reductions, and investigate what security reductions are “quantum-friendly”. We characterize sufficient conditions such that a classical reduction can be “lifted ” to the quantum setting. We then apply our lifting theorems to post-quantum signature schemes. We are able to show that the classical generic construction of hash-tree based signatures from one-way functions and and a more efficient variant proposed in [BDH11] carry over to the quantum setting. Namely, assuming existence of (classical) one-way functions that are resistant to efficient quantum inversion algorithms, there exists a quantum-secure signature scheme. We note that the scheme in [BDH11] is a promising (post-quantum) candidate to be implemented in practice and our result further justifies it. Actually, to obtain these results, we formalize a simple criteria, which is motivated by many classical proofs in the literature and is straightforward to check. This makes our lifting theorem easier to apply, and it should be useful elsewhere to prove quantum security of proposed post-quantum cryptographic schemes. Finally we demonstrate the generality of our framework by showing that several existing works (Full-Domain hash in the quantum random-oracle model [Zha12b] and the simple hybrid arguments framework in [HSS11]) can be reformulated under our unified framework. 1
One-way functions are fundamental to classical cryptography and their existence remains a longstanding problem in computational complexity theory. Recently, a provable quantum one-way function has been identified, which maintains its one-wayness even with unlimited computational resources. Here, we extend the mathematical definition of functions to construct a generalized one-way function by virtually measuring the qubit of provable quantum one-way function and randomly assigning the corresponding measurement outcomes with identical probability. Remarkably, using this generalized one-way function, we have developed an unconditionally secure key distribution protocol based solely on classical data processing, which can then utilized for secure encryption and signature. Our work highlights the importance of information in characterizing quantum systems and the physical significance of the density matrix. We demonstrate that probability theory and randomness are effective tools for countering adversaries with unlimited computational capabilities.
The existence of one-way functions is one of the most fundamental assumptions in classical cryptography. In the quantum world, on the other hand, there are evidences that some cryptographic primitives can exist even if one-way functions do not exist. We therefore have the following important open problem in quantum cryptography: What is the most fundamental element in quantum cryptography? In this direction, Brakerski, Canetti, and Qian recently defined a notion called EFI pairs, which are pairs of efficiently generatable states that are statistically distinguishable but computationally indistinguishable, and showed its equivalence with some cryptographic primitives including commitments, oblivious transfer, and general multi-party computations. However, their work focuses on decision-type primitives and does not cover search-type primitives like quantum money and digital signatures. In this paper, we study properties of one-way state generators (OWSGs), which are a quantum analogue of one-way functions. We first revisit the definition of OWSGs and generalize it by allowing mixed output states. Then we show the following results. (1) We define a weaker version of OWSGs, weak OWSGs, and show that they are equivalent to OWSGs. (2) Quantum digital signatures are equivalent to OWSGs. (3) Private-key quantum money schemes (with pure money states) imply OWSGs. (4) Quantum pseudo one-time pad schemes imply both OWSGs and EFI pairs. (5) We introduce an incomparable variant of OWSGs, which we call secretly-verifiable and statistically-invertible OWSGs, and show that they are equivalent to EFI pairs.