Paper 2025/1072
How to Model Unitary Oracles
Abstract
We make the case for modeling unitary oracles by allowing for controlled access to the oracle as well as its conjugate transpose (inverse), but also its conjugate and transpose. Controlling and conjugate transposes are common if even standard, but conjugates and transposes appear to be non-standard. In order to justify our modeling, we give several formal examples of what goes wrong or is missed when using a more restrictive modeling. We also argue that our model is the "right" level of granularity, and that other transformations likely do not correspond to efficient computation. We also discuss other modeling choices, such as ancillas and approximation error. Through our exploration, we uncover interesting phenomena. Examples include an attack on the recent pseudorandom unitary construction of Ma and Huang (STOC'25) if used incorrectly as a publicly evaluatable unitary, and a quantum complexity-theoretic separation that follows from a purely classical separation.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- A major revision of an IACR publication in CRYPTO 2025
- Keywords
- quantumoracles
- Contact author(s)
- mzhandry @ gmail com
- History
- 2025-06-09: approved
- 2025-06-07: received
- See all versions
- Short URL
- https://ia.cr/2025/1072
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/1072, author = {Mark Zhandry}, title = {How to Model Unitary Oracles}, howpublished = {Cryptology {ePrint} Archive, Paper 2025/1072}, year = {2025}, url = {https://eprint.iacr.org/2025/1072} }