Paper 2024/487
Real-Valued Somewhat-Pseudorandom Unitaries
Abstract
We explore a very simple distribution of unitaries: random (binary) phase -- Hadamard -- random (binary) phase -- random computational-basis permutation. We show that this distribution is statistically indistinguishable from random Haar unitaries for any polynomial set of orthogonal input states (in any basis) with polynomial multiplicity. This shows that even though real-valued unitaries cannot be completely pseudorandom (Haug, Bharti, Koh, arXiv:2306.11677), we can still obtain some pseudorandom properties without giving up on the simplicity of a real-valued unitary. Our analysis shows that an even simpler construction: applying a random (binary) phase followed by a random computational-basis permutation, would suffice, assuming that the input is orthogonal and flat (that is, has high min-entropy when measured in the computational basis). Using quantum-secure one-way functions (which imply quantum-secure pseudorandom functions and permutations), we obtain an efficient cryptographic instantiation of the above.
Metadata
- Available format(s)
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- PseudorandomUnitaryPRUQuantum
- Contact author(s)
-
zvika brakerski @ weizmann ac il
nir magrafta @ weizmann ac il - History
- 2024-04-16: last of 2 revisions
- 2024-03-26: received
- See all versions
- Short URL
- https://ia.cr/2024/487
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/487, author = {Zvika Brakerski and Nir Magrafta}, title = {Real-Valued Somewhat-Pseudorandom Unitaries}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/487}, year = {2024}, url = {https://eprint.iacr.org/2024/487} }