Paper 2025/1072

How to Model Unitary Oracles

Mark Zhandry, NTT Research
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.