1 of 42

Pseudorandom �Quantum States��constructions, applications, and open problems

Henry Yuen�Columbia

2 of 42

Cryptography in a quantum world

Post-Quantum Crypto

Classical crypto primitives secure�against quantum computers

Computationally-Secure

Fully Quantum Crypto

Public-key Quantum Money

Quantum Copy Protection

Pseudorandom States/Unitaries

Certified Deletion

Information-Theoretic �Fully Quantum Crypto

BB84 protocol: unconditionally-�secure key distribution, using quantum communication.

Device-independent protocols

Since this is the first talk on the first day of Qcrypt and not everyone may have heard of quantum pseudorandom states, I want to situate where it lives in the broader landscape of quantum cryptography. At a high level one can divide quantum crypto into three categories. One is post-quantum crypto, which is about designing classical crypto primitives secure against quantum computers. The second is about information-theoretic fully quantum crypto. The “fully” part means that the honest users have to have quantum capabilities. The information-theoretic part means the adversaries can be computationally unbounded; they only have to be subject to the laws of quantum mechanics. QKD is of course a flagship example of this. In the third category, we consider fully quantum crypto, but now the security of the crypto primitive assumes that the adversaries are computationally limited in power. Examples of this are pulic key quantum money and other uncloneable quantum primitives. Pseudorandom states also falls within this category.

3 of 42

Pseudorandom quantum states (PRS)

Efficiently-computable quantum states that look Haar-random to an outside observer. [Ji, Liu, Song 2018]

Applications:

Quantum cryptography

Quantum machine learning

Quantum complexity theory

Quantum gravity

4 of 42

This tutorial

Definition of pseudorandom states (PRS)

Constructions

Properties

Applications

Open questions

5 of 42

This tutorial

Definition of pseudorandom states (PRS)

Constructions

Properties

Applications

Open questions

6 of 42

A quantum analogue of pseudorandom generators

Pseudorandom Generator

Deterministic�poly-time function

Pseudorandom State Generator

Quantum�poly-time algorithm

7 of 42

Haar-random quantum states

8 of 42

Pseudorandom quantum states

9 of 42

Pseudorandom quantum states

10 of 42

Pseudorandom quantum states

11 of 42

This tutorial

Definition of pseudorandom states (PRS)

Constructions

Properties

Applications

Open questions

12 of 42

Pseudorandom states from pseudorandom functions

Theorem [Zhandry ‘12]: Post-quantum PRFs exist iff post-quantum one-way functions (OWFs) exist.

13 of 42

Pseudorandom states from pseudorandom functions

*Binary phase PRS analyzed by [Brakerski, Shmueli ‘21] [Ananth, Gulati, Qian, Y. ‘22]

Clearly efficiently computable! What about pseudorandomness?

14 of 42

Pseudorandom states from pseudorandom functions

Then, show that random binary phase states are statistically indistinguishable from Haar-random states.

15 of 42

A candidate PRS generator

16 of 42

This tutorial

Definition of pseudorandom states (PRS)

Constructions

Properties

Applications

Open questions

17 of 42

PRS are computational

18 of 42

PRG vs PRS

Pseudorandom Generator

Pseudorandom State Generator

Extremely useful in classical cryptography.

Not obvious how to use PRS for crypto.

Equivalent to OWFs.

PRS do not generically imply OWFs.

Unclear how to stretch output length of PRS generator.

Truncating output of PRG still yields PRG.

PRS are highly entangled, so cannot be truncated.

Can copy outputs of PRG.

Cannot copy PRS.

Pseudorandom states are brittle!

19 of 42

This tutorial

Definition of pseudorandom states (PRS)

Constructions

Properties

Applications

Open questions

20 of 42

Applications of classical PRGs

OWFs

PRGs

PRFs

MiniCrypt Primitives:

Private-key encryption
Commitments
Digital signatures
Zero knowledge proofs

Question: What cryptographic primitives can be constructed directly from PRS?

Classical crypto 101: PRGs are equivalent to many fundamental primitives.

Equivalences hold in classical world.

21 of 42

Applications of PRS

PRFS

Pseudo one-time pad

Commitments

Message authentication codes*

Secure�multiparty computation

PRS

Symmetric-key encryption*

*We construct PRFS from PRS under a certain parameter range.

No one-way functions needed!

One-time

Digital signatures

Pseudorandom function-like states

22 of 42

Commitments from PRS

23 of 42

Commitment schemes

Protocol executed between two mistrustful parties (committer, receiver). �Cryptographic equivalent of putting a message in sealed envelope that is opened later.

Committer

Receiver

…

24 of 42

Commitment schemes

Protocol executed between two mistrustful parties (committer, receiver). �Cryptographic equivalent of putting a message in sealed envelope that is opened later.

Committer

Receiver

…

25 of 42

Quantum commitments from PRS

26 of 42

Quantum commitments from PRS

27 of 42

Quantum commitments from PRS

28 of 42

Pseudorandom function-like states

29 of 42

Pseudorandom function-like states

[Ananth, Qian, Y. ‘22] introduced pseudorandom function-like states (PRFS).

Designed to be more flexible and less brittle than PRS.

PRFS is quantum analogue of a pseudorandom function (PRF) in

classical cryptography -- hence the name function-like.

30 of 42

Pseudorandom function-like states

31 of 42

Pseudorandom function-like states

Easy direction: PRFS generators implies the existence of PRS generators.

Constructions: Using OWFs, can build PRFS generators using Ji, Liu, Song’s construction.

Not obvious how to construct PRFS using PRS as a black box.

The famous Goldreich-Goldwasser-Micali construction that builds pseudorandom functions (PRF) from PRGs requires copying outputs. ��GGM seems incompatible with PRS!

32 of 42

PRFS from PRS

Open question: construct PRFS from PRS in a black box way.

Corollary: This Theorem is enough to build the PRFS needed for the previous applications (pseudo one-time pad, encryption).

33 of 42

Encryption from PRFS

(Private-key)

34 of 42

Pseudo one-time pad

In 1948 Shannon showed that the one-time pad achieves perfect secrecy. However, it requires a random key as long as the message.

Pseudo one-time pad: use a pseudorandom key instead from a PRG.

Can we build pseudo one-time pads from pseudorandom states?

It is not obvious! Let’s use PRFS…

35 of 42

Quantum pseudo one-time pad

36 of 42

Quantum Pseudo�One-time Pad

Looks completely random �to me…

= PRFS generator with

poly-time adversary

37 of 42

Quantum Pseudo�One-time Pad

poly-time adversary

38 of 42

Other applications of PRS

39 of 42

Other applications of PRS

Quantum complexity theory: PRS can be used to show hardness of fundamental quantum information theory tasks, such as compression of quantum states. [Bostanci, Efron, Metger, Poremba, Qian, Yuen ‘23]

Quantum complexity: PRS does not imply OWF in a black box way [Kretschmer ‘21]. In quantum world, OWFs are no longer a minimal assumption.

Quantum crypto: pseudorandom proofs of destruction [Behera, Brakerski, Sattath, Shmueli ‘23], quantum public key encryption [Coladangelo ‘23] [Barooti, Malavolta, Walter ‘23] [Grilo, Sattath, Vu ’23]….

40 of 42

Other applications of PRS

Quantum machine learning: PRS can be used to show hardness of quantum machine learning tasks. [Huang, Broughton, Cotler, et al. ‘23]

Quantum gravity: Entanglement in PRS can be ”tuned”, leading to “pseudoentanglement”. Has implications for complexity of AdS/CFT correspondence [Bouland, Fefferman, Vazirani ‘22].

Quantum pseudorandomness: PRS inspired a flurry of quantum pseudorandom primitives (EFI, OWSG, pseudorandom unitaries, …)

41 of 42

This tutorial

Definition of pseudorandom states (PRS)

Constructions

Properties

Applications

Open questions

42 of 42

Open Questions

What can be built directly from PRS in a black box way?

PRFS
Digital signatures (to sign many messages)
Symmetric key encryption (to encrypt many messages)
All of cryptomania?

2. Can we separate PRS from some quantum crypto primitives (e.g. quantum money)?

3. What are other candidate constructions of PRS, and can we give evidence for their security?

4. What is the complexity of constructing PRS? Can they be computed by log depth circuits?

5. What are other interesting quantum pseudorandom primitives?

Thank You!