On the Computational Hardness of Quantum One-Wayness
There is a large body of work studying what forms of computational hardness are needed to realize classical cryptography. In particular, one-way functions and pseudorandom generators can be built from each other, and thus require equivalent computational assumptions to be realized. Furthermore, the...
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften
2025-03-01
|
| Series: | Quantum |
| Online Access: | https://quantum-journal.org/papers/q-2025-03-27-1679/pdf/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850278016151715840 |
|---|---|
| author | Bruno Cavalar Eli Goldin Matthew Gray Peter Hall Yanyi Liu Angelos Pelecanos |
| author_facet | Bruno Cavalar Eli Goldin Matthew Gray Peter Hall Yanyi Liu Angelos Pelecanos |
| author_sort | Bruno Cavalar |
| collection | DOAJ |
| description | There is a large body of work studying what forms of computational hardness are needed to realize classical cryptography. In particular, one-way functions and pseudorandom generators can be built from each other, and thus require equivalent computational assumptions to be realized. Furthermore, the existence of either of these primitives implies that $\rm{P} \neq \rm{NP}$, which gives a lower bound on the necessary hardness.
One can also define versions of each of these primitives with quantum output: respectively one-way state generators and pseudorandom state generators. Unlike in the classical setting, it is not known whether either primitive can be built from the other. Although it has been shown that pseudorandom state generators for certain parameter regimes can be used to build one-way state generators, the implication has not been previously known in full generality. Furthermore, to the best of our knowledge, the existence of one-way state generators has no known implications in complexity theory.
We show that pseudorandom states compressing $n$ bits to $\log n + 1$ qubits can be used to build one-way state generators and pseudorandom states compressing $n$ bits to $\omega(\log n)$ qubits are one-way state generators. This is a nearly optimal result since pseudorandom states with fewer than $c \log n$-qubit output can be shown to exist unconditionally. We also show that any one-way state generator can be broken by a quantum algorithm with classical access to a $\rm{PP}$ oracle.
An interesting implication of our results is that a $t(n)$-copy one-way state generator exists unconditionally, for every $t(n) = o(n/\log n)$. This contrasts nicely with the previously known fact that $O(n)$-copy one-way state generators require computational hardness. We also outline a new route towards a black-box separation between one-way state generators and quantum bit commitments. |
| format | Article |
| id | doaj-art-c22b9ce1f76e4d29bb4e80860d9c9990 |
| institution | OA Journals |
| issn | 2521-327X |
| language | English |
| publishDate | 2025-03-01 |
| publisher | Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften |
| record_format | Article |
| series | Quantum |
| spelling | doaj-art-c22b9ce1f76e4d29bb4e80860d9c99902025-08-20T01:49:40ZengVerein zur Förderung des Open Access Publizierens in den QuantenwissenschaftenQuantum2521-327X2025-03-019167910.22331/q-2025-03-27-167910.22331/q-2025-03-27-1679On the Computational Hardness of Quantum One-WaynessBruno CavalarEli GoldinMatthew GrayPeter HallYanyi LiuAngelos PelecanosThere is a large body of work studying what forms of computational hardness are needed to realize classical cryptography. In particular, one-way functions and pseudorandom generators can be built from each other, and thus require equivalent computational assumptions to be realized. Furthermore, the existence of either of these primitives implies that $\rm{P} \neq \rm{NP}$, which gives a lower bound on the necessary hardness. One can also define versions of each of these primitives with quantum output: respectively one-way state generators and pseudorandom state generators. Unlike in the classical setting, it is not known whether either primitive can be built from the other. Although it has been shown that pseudorandom state generators for certain parameter regimes can be used to build one-way state generators, the implication has not been previously known in full generality. Furthermore, to the best of our knowledge, the existence of one-way state generators has no known implications in complexity theory. We show that pseudorandom states compressing $n$ bits to $\log n + 1$ qubits can be used to build one-way state generators and pseudorandom states compressing $n$ bits to $\omega(\log n)$ qubits are one-way state generators. This is a nearly optimal result since pseudorandom states with fewer than $c \log n$-qubit output can be shown to exist unconditionally. We also show that any one-way state generator can be broken by a quantum algorithm with classical access to a $\rm{PP}$ oracle. An interesting implication of our results is that a $t(n)$-copy one-way state generator exists unconditionally, for every $t(n) = o(n/\log n)$. This contrasts nicely with the previously known fact that $O(n)$-copy one-way state generators require computational hardness. We also outline a new route towards a black-box separation between one-way state generators and quantum bit commitments.https://quantum-journal.org/papers/q-2025-03-27-1679/pdf/ |
| spellingShingle | Bruno Cavalar Eli Goldin Matthew Gray Peter Hall Yanyi Liu Angelos Pelecanos On the Computational Hardness of Quantum One-Wayness Quantum |
| title | On the Computational Hardness of Quantum One-Wayness |
| title_full | On the Computational Hardness of Quantum One-Wayness |
| title_fullStr | On the Computational Hardness of Quantum One-Wayness |
| title_full_unstemmed | On the Computational Hardness of Quantum One-Wayness |
| title_short | On the Computational Hardness of Quantum One-Wayness |
| title_sort | on the computational hardness of quantum one wayness |
| url | https://quantum-journal.org/papers/q-2025-03-27-1679/pdf/ |
| work_keys_str_mv | AT brunocavalar onthecomputationalhardnessofquantumonewayness AT eligoldin onthecomputationalhardnessofquantumonewayness AT matthewgray onthecomputationalhardnessofquantumonewayness AT peterhall onthecomputationalhardnessofquantumonewayness AT yanyiliu onthecomputationalhardnessofquantumonewayness AT angelospelecanos onthecomputationalhardnessofquantumonewayness |