Pseudorandomness in the (Inverseless) Haar Random Oracle Model
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912085466677248 |
|---|---|
| author | Ananth, Prabhanjan Bostanci, John Gulati, Aditya Lin, Yao-Ting |
| author_facet | Ananth, Prabhanjan Bostanci, John Gulati, Aditya Lin, Yao-Ting |
| contents | We study the (in)feasibility of quantum pseudorandom notions in a quantum analog of the random oracle model, where all the parties, including the adversary, have oracle access to the same Haar random unitary. In this model, we show the following:
- (Unbounded-query secure) pseudorandom unitaries (PRU) exist. Moreover, the PRU construction makes two calls to the Haar oracle.
- We consider constructions of PRUs making a single call to the Haar oracle. In this setting, we show that unbounded-query security is impossible to achieve. We complement this result by showing that bounded-query secure PRUs do exist with a single query to the Haar oracle.
- We show that multi-copy pseudorandom state generators and function-like state generators (with classical query access), making a single call to the Haar oracle, exist.
Our results have two consequences: (a) when the Haar random unitary is instantiated suitably, our results present viable approaches for building quantum pseudorandom objects without relying upon one-way functions and, (b) for the first time, we show that the key length in pseudorandom unitaries can be generically shrunk (relative to the output length). Our results are also some of the first usecases of the new "path recording" formalism for Haar random unitaries, introduced in the recent breakthrough work of Ma and Huang. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_19320 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Pseudorandomness in the (Inverseless) Haar Random Oracle Model Ananth, Prabhanjan Bostanci, John Gulati, Aditya Lin, Yao-Ting Quantum Physics Computational Complexity Cryptography and Security We study the (in)feasibility of quantum pseudorandom notions in a quantum analog of the random oracle model, where all the parties, including the adversary, have oracle access to the same Haar random unitary. In this model, we show the following: - (Unbounded-query secure) pseudorandom unitaries (PRU) exist. Moreover, the PRU construction makes two calls to the Haar oracle. - We consider constructions of PRUs making a single call to the Haar oracle. In this setting, we show that unbounded-query security is impossible to achieve. We complement this result by showing that bounded-query secure PRUs do exist with a single query to the Haar oracle. - We show that multi-copy pseudorandom state generators and function-like state generators (with classical query access), making a single call to the Haar oracle, exist. Our results have two consequences: (a) when the Haar random unitary is instantiated suitably, our results present viable approaches for building quantum pseudorandom objects without relying upon one-way functions and, (b) for the first time, we show that the key length in pseudorandom unitaries can be generically shrunk (relative to the output length). Our results are also some of the first usecases of the new "path recording" formalism for Haar random unitaries, introduced in the recent breakthrough work of Ma and Huang. |
| title | Pseudorandomness in the (Inverseless) Haar Random Oracle Model |
| topic | Quantum Physics Computational Complexity Cryptography and Security |
| url | https://arxiv.org/abs/2410.19320 |