# Cryptography from Pseudorandom Quantum States

arXiv: https://arxiv.org/abs/2112.10020 · HTML: https://mlsanity.com/paper/2112.10020/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Dec 2021.

## Built on by (most cited first, 6 of 6)

- [A survey on the complexity of learning quantum states](https://mlsanity.com/paper/2305.20069/) (2023)
- [Estimating the randomness of quantum circuit ensembles up to 50 qubits](https://mlsanity.com/paper/2205.09900/) (2022)
- [Unclonability and Quantum Cryptanalysis: From Foundations to Applications](https://mlsanity.com/paper/2210.17545/) (2022)
- [A quantum tug of war between randomness and symmetries on homogeneous spaces](https://mlsanity.com/paper/2309.05253/) (2023)
- [Noise-tolerant learnability of shallow quantum circuits from statistics and the cost of quantum pseudorandomness](https://mlsanity.com/paper/2405.12085/) (2024)
- [Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more](https://mlsanity.com/paper/2510.06848/) (2025)

## Abstract (arXiv)

Pseudorandom states, introduced by Ji, Liu and Song (Crypto'18), are efficiently-computable quantum states that are computationally indistinguishable from Haar-random states. One-way functions imply the existence of pseudorandom states, but Kretschmer (TQC'20) recently constructed an oracle relative to which there are no one-way functions but pseudorandom states still exist. Motivated by this, we study the intriguing possibility of basing interesting cryptographic tasks on pseudorandom states. We construct, assuming the existence of pseudorandom state generators that map a λ-bit seed to a ω(logλ)-qubit state, (a) statistically binding and computationally hiding commitments and (b) pseudo one-time encryption schemes. A consequence of (a) is that pseudorandom states are sufficient to construct maliciously secure multiparty computation protocols in the dishonest majority setting. Our constructions are derived via a new notion called pseudorandom function-like states (PRFS), a generalization of pseudorandom states that parallels the classical notion of pseudorandom functions. Beyond the above two applications, we believe our notion can effectively replace pseudorandom functions in many other cryptographic applications.