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

arXiv:2209.10146

Creating quantum-resistant classical-classical OWFs from quantum-classical OWFs

Wei Zheng Teo, Marco Carmosino, Lior Horesh C

Published Sep 21, 2022• 0 citations
arXivHTMLPDF

Abstract

One-way functions (OWF) are one of the most essential cryptographic primitives, the existence of which results in wide-ranging ramifications such as private-key encryption and proving $P \neq NP$. These OWFs are often thought of as having classical input and output (i.e. binary strings), however, recent work proposes OWF constructions where the input and/or the output can be quantum. In this paper, we demonstrate that quantum-classical (i.e. quantum input, classical output) OWFs can be used to produce classical-classical (i.e. classical input, classical output) OWFs that retain the one-wayness property against any quantum polynomial adversary (i.e. quantum-resistant). We demonstrate this in two ways. Firstly, we propose a definition of quantum-classical OWFs and show that the existence of such a quantum-classical OWF would imply the existence of a classical-classical OWF. Secondly, we take a proposed quantum-classical OWF and demonstrate how to turn it into a classical-classical OWF. In summary, this paper showcases another possible route into proving the existence of classical-classical OWFs (assuming intermediate quantum computations are allowed) using a "domain-shifting" technique between classical and quantum information, with the added bonus that such OWFs are also going to be quantum-resistant.

DOI
10.48550/arxiv.2209.10146

Related papers

A Note on the Minimality of One-Way Functions in Post-Quantum Cryptography

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.

IACR Communications in Cryptology•Jan 13, 2025•0 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•20 citations

Cryptographic quantum hashing

Farid Mansurovich Ablayev, Alexander Vasiliev

We present a version of quantum hash functions based on non-binary discrete functions. The proposed quantum procedure is 'classical-quantum', that is, it takes a classical bit string as an input and produces a quantum state. The resulting function has the property of a one-way function (pre-image resistance); in addition it has properties analogous to classical cryptographic hash second pre-image resistance and collision resistance. We also show that the proposed function can be naturally used in a quantum digital signature protocol.

Laser Physics Letters•Dec 24, 2013•70 citations

Quantum Cryptomania with Classical Communication without One-Way Functions

Mohammed Barhoush, Amit Behera

In classical cryptography, one-way functions are necessary for most of cryptography. In the quantum world, however, Kretschmer at {TQC'21} and subsequent works have demonstrated that quantum versions of various primitives in minicrypt, such as signatures and private-key encryption, do not require quantum-computable one-way functions (\textsf{qOWF}s). However, the question of the necessity of \textsf{qOWF}s for primitives in Cryptomania like public-key encryption with classical public keys and ciphertexts (\textsf{qPKE}) has remained open. We provide a comprehensive picture of the relationship between \textsf{qPKE} and \textsf{qOWF}. First, our main result is a black-box separation between \textsf{qOWF}s and \textsf{qPKE}. In particular, we show that relative to a unitary, real, and self-inverse oracle, there exists a \textsf{qPKE} scheme (with classical keys and ciphertexts), but \textsf{qOWF}s do not exist. Further, our oracles admit a point-function obfuscation construction, thus ruling out black-box construction of \textsf{qOWF} from point function obfuscations. On the positive side, we construct \textsf{qPKE} from quantum indistinguishability obfuscation for quantum circuits with classical obfuscated descriptions and efficiently verifiable one-way puzzles, which is known to be a potentially weaker assumption than \textsf{qOWF}s, due to an existing black-box separation. Our construction is the quantum analog of the classical construction of \textsf{PKE} from one-way functions and indistinguishability obfuscation in the quantum computation with classical communication (QCCC) setting.

quant-pharXiv:2610.32145•Oct 26, 2026•0 citations

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

Secure Quantum Two-Party Computation: Impossibility and Constructions.

Michele Ciampi, Alexandru Cojocaru, Elham Kashefi +1 more

Secure two-party computation considers the problem of two parties computing a joint function of their private inputs without revealing anything beyond the output of the computation. In this work, we take the first steps towards understanding the setting in which the two parties want to evaluate a joint quantum functionality while using only a classical channel between them. Our first result indicates that it is in general impossible to realize a two-party quantum functionality against malicious adversaries with black-box simulation, relying only on classical channels. The negative result stems from reducing the existence of a black-box simulator to an extractor for classical proof of quantum knowledge, which in turn leads to violation of the quantum no-cloning. Next, we introduce the notion of oblivious quantum function evaluation (OQFE). An OQFE is a two-party quantum cryptographic primitive with one fully classical party (Alice) whose input is (a classical description of a) quantum unitary, $U$, and a quantum party (Bob) whose input is a quantum state, $\psi$. In particular, Alice receives a classical output corresponding to the measurement of $U(\psi)$ while Bob receives no output. In OQFE, Bob remains oblivious to Alice's input, while Alice learns nothing about $\psi$ more than what can be learned from the output. We present two constructions, one secure against semi-honest parties and the other against malicious parties. Due to the no-go result mentioned above, we consider what is arguably the best possible notion obtainable in our model concerning malicious adversaries: one-sided simulation security. Our protocol relies on the assumption of injective homomorphic trapdoor OWFs, which in turn rely on the LWE problem. As a result, we put forward a first, simple and modular, construction of one-sided quantum two-party computation and quantum oblivious transfer over classical networks.

•Jan 1, 2020•1 citation
One-way functions (OWF) are one of the most essential cryptographic primitives, the existence of which results in wide-ranging ramifications such as private-key encryption and proving P≠NPP \neq NPP=NP. These OWFs are often thought of as having classical input and output (i.e. binary strings), however, recent work proposes OWF constructions where the input and/or the output can be quantum. In this paper, we demonstrate that quantum-classical (i.e. quantum input, classical output) OWFs can be used to produce classical-classical (i.e. classical input, classical output) OWFs that retain the one-wayness property against any quantum polynomial adversary (i.e. quantum-resistant). We demonstrate this in two ways. Firstly, we propose a definition of quantum-classical OWFs and show that the existence of such a quantum-classical OWF would imply the existence of a classical-classical OWF. Secondly, we take a proposed quantum-classical OWF and demonstrate how to turn it into a classical-classical OWF. In summary, this paper showcases another possible route into proving the existence of classical-classical OWFs (assuming intermediate quantum computations are allowed) using a "domain-shifting" technique between classical and quantum information, with the added bonus that such OWFs are also going to be quantum-resistant.
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.
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.
We present a version of quantum hash functions based on non-binary discrete functions. The proposed quantum procedure is 'classical-quantum', that is, it takes a classical bit string as an input and produces a quantum state. The resulting function has the property of a one-way function (pre-image resistance); in addition it has properties analogous to classical cryptographic hash second pre-image resistance and collision resistance. We also show that the proposed function can be naturally used in a quantum digital signature protocol.
In classical cryptography, one-way functions are necessary for most of cryptography. In the quantum world, however, Kretschmer at {TQC'21} and subsequent works have demonstrated that quantum versions of various primitives in minicrypt, such as signatures and private-key encryption, do not require quantum-computable one-way functions (\textsf{qOWF}s). However, the question of the necessity of \textsf{qOWF}s for primitives in Cryptomania like public-key encryption with classical public keys and ciphertexts (\textsf{qPKE}) has remained open. We provide a comprehensive picture of the relationship between \textsf{qPKE} and \textsf{qOWF}. First, our main result is a black-box separation between \textsf{qOWF}s and \textsf{qPKE}. In particular, we show that relative to a unitary, real, and self-inverse oracle, there exists a \textsf{qPKE} scheme (with classical keys and ciphertexts), but \textsf{qOWF}s do not exist. Further, our oracles admit a point-function obfuscation construction, thus ruling out black-box construction of \textsf{qOWF} from point function obfuscations. On the positive side, we construct \textsf{qPKE} from quantum indistinguishability obfuscation for quantum circuits with classical obfuscated descriptions and efficiently verifiable one-way puzzles, which is known to be a potentially weaker assumption than \textsf{qOWF}s, due to an existing black-box separation. Our construction is the quantum analog of the classical construction of \textsf{PKE} from one-way functions and indistinguishability obfuscation in the quantum computation with classical communication (QCCC) setting.
Secure two-party computation considers the problem of two parties computing a joint function of their private inputs without revealing anything beyond the output of the computation. In this work, we take the first steps towards understanding the setting in which the two parties want to evaluate a joint quantum functionality while using only a classical channel between them. Our first result indicates that it is in general impossible to realize a two-party quantum functionality against malicious adversaries with black-box simulation, relying only on classical channels. The negative result stems from reducing the existence of a black-box simulator to an extractor for classical proof of quantum knowledge, which in turn leads to violation of the quantum no-cloning. Next, we introduce the notion of oblivious quantum function evaluation (OQFE). An OQFE is a two-party quantum cryptographic primitive with one fully classical party (Alice) whose input is (a classical description of a) quantum unitary, UUU, and a quantum party (Bob) whose input is a quantum state, ψ\psiψ. In particular, Alice receives a classical output corresponding to the measurement of U(ψ)U(\psi)U(ψ) while Bob receives no output. In OQFE, Bob remains oblivious to Alice's input, while Alice learns nothing about ψ\psiψ more than what can be learned from the output. We present two constructions, one secure against semi-honest parties and the other against malicious parties. Due to the no-go result mentioned above, we consider what is arguably the best possible notion obtainable in our model concerning malicious adversaries: one-sided simulation security. Our protocol relies on the assumption of injective homomorphic trapdoor OWFs, which in turn rely on the LWE problem. As a result, we put forward a first, simple and modular, construction of one-sided quantum two-party computation and quantum oblivious transfer over classical networks.