Paper 2024/487

Real-Valued Somewhat-Pseudorandom Unitaries

Zvika Brakerski, Weizmann Institute of Science
Nir Magrafta, Weizmann Institute of Science
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)
PDF
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.