International Association
for Cryptologic Research

We introduce a new notion called $\mathcal{Q}$-secure pseudorandom isometries (PRI). A pseudorandom isometry is an efficient quantum circuit that maps an $n$-qubit state to an $(n+m)$-qubit state in an isometric manner. In terms of security, we require that the output of a $q$-fold PRI on $\rho$, for $ \rho \in \mathcal{Q}$, for any polynomial $q$, should be computationally indistinguishable from the output of a $q$-fold Haar isometry on $\rho$. By fine-tuning $\mathcal{Q}$, we recover many existing notions of pseudorandomness. We present a construction of PRIs and assuming post-quantum one-way functions, we prove the security of $\mathcal{Q}$-secure pseudorandom isometries (PRI) for different interesting settings of $\mathcal{Q}$. We also demonstrate many cryptographic applications of PRIs, including, length extension theorems for quantum pseudorandomness notions, MACs for quantum states, multi-copy secure public and private encryption schemes, and succinct quantum commitments.

Pseudorandom quantum states (PRS) are efficiently constructible states that are computationally indistinguishable from being Haar-random, and have recently found cryptographic applications. We explore new definitions and applications of pseudorandom states, and present the following contributions: - We study variants of pseudorandom \emph{function-like} state (PRFS) generators, introduced by Ananth, Qian, and Yuen (CRYPTO'22), where the pseudorandomness property holds even when the generator can be queried adaptively or in superposition. We show feasibility of these variants assuming the existence of post-quantum one-way functions. - We show that PRS generators with logarithmic output length imply commitment and encryption schemes with \emph{classical communication}. Previous constructions of such schemes from PRS generators required quantum communication. - We give a simpler proof of the Brakerski--Shmueli (TCC'19) result that polynomially-many copies of uniform superposition states with random binary phases are indistinguishable from Haar-random states. - We also show that logarithmic output length is a sharp threshold where PRS generators start requiring computational assumptions.