Welcome to the resource topic for 2024/302
Title:
Pseudorandom unitaries with non-adaptive security
Authors: Tony Metger, Alexander Poremba, Makrand Sinha, Henry Yuen
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.
ePrint: https://eprint.iacr.org/2024/302
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .