Paper 2024/302

Pseudorandom unitaries with non-adaptive security

Tony Metger, ETH Zurich
Alexander Poremba, Massachusetts Institute of Technology
Makrand Sinha, University of Illinois Urbana-Champaign
Henry Yuen, Columbia University
Abstract

Pseudorandom unitaries (PRUs) are ensembles of efficiently implementable unitary operators that cannot be distinguished from Haar random unitaries by any quantum polynomial-time algorithm with query access to the unitary. We present a simple PRU construction that is a concatenation of a random Clifford unitary, a pseudorandom binary phase operator, and a pseudorandom permutation operator. We prove that this PRU construction is secure against non-adaptive distinguishers assuming the existence of quantum-secure one-way functions. This means that no efficient quantum query algorithm that is allowed a single application of $U^{\otimes \mathrm{poly}(n)}$ can distinguish whether an $n$-qubit unitary $U$ was drawn from the Haar measure or our PRU ensemble. We conjecture that our PRU construction remains secure against adaptive distinguishers, i.e., secure against distinguishers that can query the unitary polynomially many times in sequence, not just in parallel.

Note: 17 pages.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
quantum cryptographypseudorandom unitaries
Contact author(s)
tmetger @ ethz ch
poremba @ mit edu
msinha @ illinois edu
henry yuen @ columbia edu
History
2024-02-23: approved
2024-02-22: received
See all versions
Short URL
https://ia.cr/2024/302
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/302,
      author = {Tony Metger and Alexander Poremba and Makrand Sinha and Henry Yuen},
      title = {Pseudorandom unitaries with non-adaptive security},
      howpublished = {Cryptology ePrint Archive, Paper 2024/302},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/302}},
      url = {https://eprint.iacr.org/2024/302}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.