Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2510.05055 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908578255732736 |
|---|---|
| author | Cakan, Alper Khurana, Dakshita Morimae, Tomoyuki Shirakawa, Yuki Tomer, Kabir Yamakawa, Takashi |
| author_facet | Cakan, Alper Khurana, Dakshita Morimae, Tomoyuki Shirakawa, Yuki Tomer, Kabir Yamakawa, Takashi |
| contents | We investigate quantum analogues of collision resistance and obtain separations between quantum ``one-way'' and ``collision-resistant'' primitives.
1. Our first result studies one-wayness versus collision-resistance defined over quantum circuits that output classical strings. We show that there is a classical oracle $\mathcal{O}$ relative to which (sub-exponentially secure) indistinguishability obfuscation and one-way permutations exist even against adversaries that make quantum queries to a non-collapsing measurement oracle, $\mathcal{Q}^{\mathcal{O}}$. Very roughly, $\mathcal{Q}^{\mathcal{O}}$ outputs the result of multiple non-collapsing measurements on the output of any quantum $\mathcal{O}$-aided circuit.
This rules out fully black-box {\em quantum} constructions of $Y$ from $X$ for any $X \in \{$indistinguishability obfuscation and one-way permutations, public-key encryption, deniable encryption, oblivious transfer, non-interactive ZK, trapdoor permutations, quantum money$\}, Y \in \{$collision-resistant hash functions, hard problems in SZK, homomorphic encryption, distributional collision-resistant puzzles$\}$.
2. Our second result studies one-wayness versus collision-resistance defined over quantum states. Here, we show that relative to the same classical oracle $\mathcal{O}$, (sub-exponentially secure) indistinguishability obfuscation and one-way permutations exist even against adversaries that make quantum queries to a {\em cloning unitary} $\mathsf{QCol}^\mathcal{O}$. Very roughly, this latter oracle implements a well-defined, linear operation to clone a subset of the qubits output by any quantum $\mathcal{O}$-aided circuit.
This rules out fully black-box constructions of quantum lightning from public-key quantum money. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_05055 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Cryptographic Futility of Non-Collapsing Measurements Cakan, Alper Khurana, Dakshita Morimae, Tomoyuki Shirakawa, Yuki Tomer, Kabir Yamakawa, Takashi Quantum Physics We investigate quantum analogues of collision resistance and obtain separations between quantum ``one-way'' and ``collision-resistant'' primitives. 1. Our first result studies one-wayness versus collision-resistance defined over quantum circuits that output classical strings. We show that there is a classical oracle $\mathcal{O}$ relative to which (sub-exponentially secure) indistinguishability obfuscation and one-way permutations exist even against adversaries that make quantum queries to a non-collapsing measurement oracle, $\mathcal{Q}^{\mathcal{O}}$. Very roughly, $\mathcal{Q}^{\mathcal{O}}$ outputs the result of multiple non-collapsing measurements on the output of any quantum $\mathcal{O}$-aided circuit. This rules out fully black-box {\em quantum} constructions of $Y$ from $X$ for any $X \in \{$indistinguishability obfuscation and one-way permutations, public-key encryption, deniable encryption, oblivious transfer, non-interactive ZK, trapdoor permutations, quantum money$\}, Y \in \{$collision-resistant hash functions, hard problems in SZK, homomorphic encryption, distributional collision-resistant puzzles$\}$. 2. Our second result studies one-wayness versus collision-resistance defined over quantum states. Here, we show that relative to the same classical oracle $\mathcal{O}$, (sub-exponentially secure) indistinguishability obfuscation and one-way permutations exist even against adversaries that make quantum queries to a {\em cloning unitary} $\mathsf{QCol}^\mathcal{O}$. Very roughly, this latter oracle implements a well-defined, linear operation to clone a subset of the qubits output by any quantum $\mathcal{O}$-aided circuit. This rules out fully black-box constructions of quantum lightning from public-key quantum money. |
| title | On the Cryptographic Futility of Non-Collapsing Measurements |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2510.05055 |