Permutation Superposition Oracles for Quantum Query Lower Bounds
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912653147897856 |
|---|---|
| author | Majenz, Christian Malavolta, Giulio Walter, Michael |
| author_facet | Majenz, Christian Malavolta, Giulio Walter, Michael |
| contents | We propose a generalization of Zhandry's compressed oracle method to random permutations, where an algorithm can query both the permutation and its inverse. We show how to use the resulting oracle simulation to bound the success probability of an algorithm for any predicate on input-output pairs, a key feature of Zhandry's technique that had hitherto resisted attempts at generalization to random permutations. One key technical ingredient is to use strictly monotone factorizations to represent the permutation in the oracle's database. As an application of our framework, we show that the one-round sponge construction is unconditionally preimage resistant in the random permutation model. This proves a conjecture by Unruh. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_09655 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Permutation Superposition Oracles for Quantum Query Lower Bounds Majenz, Christian Malavolta, Giulio Walter, Michael Quantum Physics Cryptography and Security We propose a generalization of Zhandry's compressed oracle method to random permutations, where an algorithm can query both the permutation and its inverse. We show how to use the resulting oracle simulation to bound the success probability of an algorithm for any predicate on input-output pairs, a key feature of Zhandry's technique that had hitherto resisted attempts at generalization to random permutations. One key technical ingredient is to use strictly monotone factorizations to represent the permutation in the oracle's database. As an application of our framework, we show that the one-round sponge construction is unconditionally preimage resistant in the random permutation model. This proves a conjecture by Unruh. |
| title | Permutation Superposition Oracles for Quantum Query Lower Bounds |
| topic | Quantum Physics Cryptography and Security |
| url | https://arxiv.org/abs/2407.09655 |