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

Springer eBooks

Quantum One-Way Function

Tao Shang

Published Oct 15, 2024• 0 citations
Publisher
DOI
10.1007/978-981-97-6722-9_8

Related papers

Quantum Advantage from One-Way Functions

Tomoyuki Morimae, Takashi Yamakawa

arXiv:2302.04749•Lecture notes in computer science•Jan 1, 2024•9 citations

Universal construction of a full quantum one-way function

Yao Tang, Tao Shang, Jianwei Liu

Quantum Information Processing•Jul 26, 2022•4 citations

Commitments are Equivalent to Statistically-Verifiable One-Way State Generators

Rishabh Batra, Rahul Jain

One-way state generators (OWSG) [1] are natural quantum analogs to classical one-way functions. We consider statistically-verifiable OWSGs (sv-OWSG), which are potentially weaker objects than OWSGs. We show that$O\left(\frac{n}{\log (n)}\right)$-copy sv-OWSGs ($n$represents the input length) are equivalent to$poly (n)$-copy sv-OWSGs and to quantum commitments. Since known results show that$o\left(\frac{n}{\log (n)}\right)$-copy OWSGs cannot imply commitments [2], this shows that$O\left(\frac{n}{\log(n)}\right)$-copy sv-OWSGs are the weakest OWSGs from which we can get commitments (and hence much of quantum cryptography). Our construction follows along the lines of Hastad, Impagliazzo, Levin and Luby [3], who obtained classical pseudorandom generators (PRG) from classical one-way functions (OWF), however with crucial modifications. Our construction, when applied to the classical case, provides an alternative to the construction provided by [3] to obtain a classical mildly non-uniform PRG from any classical OWF. Since we do not argue conditioned on the output$f(x)$, our construction and analysis is arguably simpler and may be of independent interest. For converting a mildly non-uniform PRG to a uniform PRG, we can use the same construction as [3].

arXiv:2404.03220•Annual Symposium on Foundations of Computer Science•Oct 27, 2024•19 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

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

Wei Zheng Teo, Marco Carmosino, Lior Horesh C

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.

arXiv:2209.10146•Sep 21, 2022•0 citations

One-Way Quantumness

Anonymous

Physics•Apr 21, 2016•0 citations
One-way state generators (OWSG) [1] are natural quantum analogs to classical one-way functions. We consider statistically-verifiable OWSGs (sv-OWSG), which are potentially weaker objects than OWSGs. We show thatO(nlog⁡(n))O\left(\frac{n}{\log (n)}\right)O(log(n)n​)-copy sv-OWSGs (nnnrepresents the input length) are equivalent topoly(n)poly (n)poly(n)-copy sv-OWSGs and to quantum commitments. Since known results show thato(nlog⁡(n))o\left(\frac{n}{\log (n)}\right)o(log(n)n​)-copy OWSGs cannot imply commitments [2], this shows thatO(nlog⁡(n))O\left(\frac{n}{\log(n)}\right)O(log(n)n​)-copy sv-OWSGs are the weakest OWSGs from which we can get commitments (and hence much of quantum cryptography). Our construction follows along the lines of Hastad, Impagliazzo, Levin and Luby [3], who obtained classical pseudorandom generators (PRG) from classical one-way functions (OWF), however with crucial modifications. Our construction, when applied to the classical case, provides an alternative to the construction provided by [3] to obtain a classical mildly non-uniform PRG from any classical OWF. Since we do not argue conditioned on the outputf(x)f(x)f(x), our construction and analysis is arguably simpler and may be of independent interest. For converting a mildly non-uniform PRG to a uniform PRG, we can use the same construction as [3].
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.
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.