Paper 2025/1785
On the Limitations of Pseudorandom Unitaries
Abstract
Pseudorandom unitaries (PRUs), one of the key quantum pseudorandom notions, are efficiently computable unitaries that are computationally indistinguishable from Haar random unitaries. While there is evidence to believe that PRUs are weaker than one-way functions, so far its relationship with other quantum cryptographic primitives (that are plausibly weaker than one-way functions) has not been fully established. In this work, we focus on quantum cryptographic primitives with classical communication, referred to as QCCC primitives. Our main result shows that QCCC bit commitments and QCCC key agreement, cannot be constructed from pseudorandom unitaries in a black-box manner. Our core technical contribution is to show (in a variety of settings) the difficulty of distinguishing identical versus independent Haar unitaries by separable channels. Our result strictly improves upon prior works which studied similar problems in the context of learning theory [Anshu, Landau, Liu, STOC 2022] and cryptography [Ananth, Gulati, Lin, TCC 2024].
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published by the IACR in TCC 2025
- Contact author(s)
-
prabhanjan @ cs ucsb edu
adityagulati @ ucsb edu
yao-ting_lin @ ucsb edu - History
- 2025-10-03: approved
- 2025-09-29: received
- See all versions
- Short URL
- https://ia.cr/2025/1785
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/1785,
author = {Prabhanjan Ananth and Aditya Gulati and Yao-Ting Lin},
title = {On the Limitations of Pseudorandom Unitaries},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/1785},
year = {2025},
url = {https://eprint.iacr.org/2025/1785}
}
