Pseudorandom Unitaries in the Haar Random Oracle Model A preliminary version of a merge of this paper and [ ABGL25 ] appears in the proceedings of the 45th Annual International Cryptology Conference ( CRYPTO 2025 ) [ ABGL25a ] . This is Part I of the full version.

Prabhanjan Ananth, John Bostanci, Aditya Gulati, Yao-Ting Lin · 2025

Read Pseudorandom Unitaries in the Haar Random Oracle Model A preliminary version of a merge of this paper and [ ABGL25 ] appears in the proceedings of the 45th Annual International Cryptology Conference ( CRYPTO 2025 ) [ ABGL25a ] . This is Part I of the full version. by Prabhanjan Ananth, John Bostanci, Aditya Gulati, Yao-Ting Lin (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-24432.txt.

Introduction

Prabhanjan Ananth and 3 co-authors build strong pseudorandom unitaries inside an idealized quantum setting. In the Haar random oracle model, every party can query one perfectly random unitary and its inverse. Pseudorandom unitaries must look random to any efficient test yet be cheap to build, a core tool for quantum cryptography.

Earlier work proved such objects exist only without the inverse, or proved a weaker notion with it. This construction is the first strong version in the full model. The authors also frame it as a viable route to quantum pseudorandomness from random circuits. The result speaks to how pseudorandom objects behave in nature as well.

Catalog record

CREATORPrabhanjan Ananth, John Bostanci, Aditya Gulati, Yao-Ting Lin
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE229 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-24432

Browse the full library · About the Tower of Babel