1 of 40

Cryptography from Pseudorandom Quantum States

Prabhanjan Ananth �UC Santa Barbara

Luowen Qian�Boston University

Henry Yuen�Columbia

2 of 40

Cryptography: dazzling possibilities

Encryption

Bit commitment

Coin Flipping

Program Obfuscation

Digital Signatures

Secure Multiparty Computation

Homomorphic�Encryption

Zero-Knowledge

3 of 40

Cryptography: dazzling possibilities

Encryption

Bit commitment

Coin Flipping

Program Obfuscation

Digital Signatures

Secure Multiparty Computation

Homomorphic�Encryption

Zero-Knowledge

Amazing possibilities rely on�hardness assumptions: some computational task is difficult for all resource-limited adversaries.

4 of 40

The Zoo of Assumptions

One-way functions

Pseudorandom Generators

Hardness of�factoring

LPN

Hardness of lattice problems

DDH

Trapdoor�One-way functions

RSA

SXDH

LWE

SVP

DCR

rand(t)

Cryptographers have also developed a whole zoo of hardness assumptions as well. The most basic ones are the existence of objects known as OWFs and PRGs. A OWF is a function that you can efficiently compute in the forward direction, but it is very hard the other way. A PRG is something that takes a short random seed to produce a much larger pseudorandom looking sequence of bits. There are assumptions on the hardness of solving specific computational problems; the most famous one of these is the assumption that it is hard to factor integers on a computer, which underlies the security of the most commonly used cryptosystem. Of course many of us know that this assumption is no longer valid in the presence of quantum computers. There are many other assumptions that cryptographers study, and after a while it starts to resemble alphabet soup…

5 of 40

The Zoo of Assumptions

One-way functions

Pseudorandom Generators

Hardness of�factoring

LPN

Hardness of lattice problems

DDH

Trapdoor�One-way functions

RSA

SXDH

LWE

SVP

DCR

rand(t)

OWFs: (provably) minimal crypto assumption. �Necessary assumption for cryptography.

…at least, for classical protocols.

6 of 40

Cryptography in a quantum world

Quantum Key Distribution

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

Classical key distribution requires assumptions stronger than OWFs.

Shor’s Algorithm

Quantum computers can factor integers in poly time.��Security of RSA assumes hardness of factoring.

(More) Recent �Developments

Public-key Quantum Money

Quantum Copy Protection

Device-Independent Protocols

Secure Multiparty Computation � based only on OWFs� + quantum communication

But we live in a world where, increasingly, we’re able to process, transmit, and compute with quantum data. So we can try to leverage the laws of quantum physics to see what’s possible in cryptography. An this can drastically revise our understanding of what hardness assumptions are necessary for cryptography in the quantum world. The most famous example of this is quantum key distribution, such as the BB84 protocol, which enables to parties to use quantum communication over a public channel to establish a secret key between themselves. This can be performed without any hardness assumptions – the security only relies on the laws of physics, so to speak. In contrast, classical key distribution requires assumptions even stronger than OWFs. ��Another famous example is Shor’s Algorithm, which can factor integers on a quantum computer in polynomial time. As I mentioned before, this means that the hardness assumption underlying RSA is no longer valid.

7 of 40

Cryptography in a quantum world

Quantum Key Distribution

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

Classical key distribution requires assumptions stronger than OWFs.

Shor’s Algorithm

Quantum computers can factor integers in poly time.��Security of RSA assumes hardness of factoring.

Public-key Quantum Money

Quantum Copy Protection

Device-Independent Protocols

Secure Multiparty Computation � based only on OWFs

+ quantum communication

What are the minimal assumptions needed for cryptography in the quantum world?

(More) Recent �Developments

8 of 40

This talk

We show that “Crypto 101” tasks, such as�

(Private-key) encryption
Bit commitment
Zero-knowledge proofs for NP
Secure multiparty computation

can be performed using pseudorandom quantum states (PRS), rather than one-way functions.

PRS can provide an �alternative foundation for security of cryptographic tasks.

9 of 40

Pseudorandom Quantum States

10 of 40

A quantum analogue of pseudorandom generators

Pseudorandom Generator

Deterministic�poly-time function

Pseudorandom State Generator

Quantum�poly-time algorithm

11 of 40

Haar-random quantum states

12 of 40

Pseudorandom quantum states

13 of 40

Pseudorandom quantum states

14 of 40

Pseudorandom quantum states

15 of 40

A candidate PRS generator

16 of 40

Pseudorandom quantum states

Pseudorandom states are efficient imitators of Haar-random states.

2018: Zhengfeng Ji, Yi-Kai Liu, Fang Song defined PRS as quantum analogue of PRGs.

Construction: PRS generators can be constructed from one-way functions (OWFs).

Cryptographic applications: Private-key quantum money schemes.

2021: William Kretschmer showed OWFs cannot be constructed from PRS �in generic, black-box way.

In quantum crypto, PRS may be more fundamental than OWFs!

17 of 40

Pseudorandom quantum states

Pseudorandom states are efficient imitators of Haar-random states.

2018: Zhengfeng Ji, Yi-Kai Liu, Fang Song defined PRS as quantum analogue of PRGs.

Construction: PRS generators can be constructed from one-way functions (OWFs).

Cryptographic applications: Private-key quantum money schemes.

2021: William Kretschmer showed OWFs cannot be constructed from PRS �in generic, black-box way.

In quantum crypto, PRS may be more fundamental than OWFs!

What cryptography can be built from pseudorandom quantum states?

18 of 40

PRG vs PRS

Pseudorandom Generator

Pseudorandom State Generator

Extremely useful in classical cryptography.

Unclear how to use PRS for crypto.

Equivalent to OWFs.

OWFs do not generically imply PRS.

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 40

Pseudorandom function-like states

We introduce a new notion: 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.

20 of 40

Pseudorandom function-like states

21 of 40

Pseudorandom function-like states

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

Harder direction: 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 classical pseudorandom functions (PRF) from PRGs requires copying outputs. ��GGM seems incompatible with PRS!

22 of 40

Applications of PRFS

PRFS

Pseudo one-time pad

Bit commitment

Message authentication codes*

Secure�multiparty computation

PRS

Symmetric-key encryption*

Work of �Bartusek-Coladangelo-Khurana-Ma ‘21

We construct PRFS from PRS under a certain parameter range.

Look Ma -- no one-way functions!

Also (concurrently) obtained from PRS by Morimae-Yamakawa ’21.

23 of 40

Encryption from PRFS

(Private-key)

24 of 40

Private-key �Encryption

= shared random key

Looks completely random �to me…

adversary

25 of 40

One-time Pad

Looks completely random �to me…

unbounded adversary

26 of 40

Pseudo�One-time Pad

Still looks completely random �to me…

poly-time adversary

27 of 40

Pseudo�One-time Pad

Still looks completely random �to me…

poly-time adversary

Using PRG, can imitate one-time pad with shorter key (assuming poly-time adversary).

28 of 40

Pseudo�One-time Pad

Still looks completely random �to me…

poly-time adversary

Natural idea: replace PRG with PRS gen? �Doesn’t work: e.g., no obvious way to decode.

29 of 40

Quantum Pseudo�One-time Pad

Still looks completely random �to me…

= PRFS generator with

poly-time adversary

30 of 40

Quantum Pseudo�One-time Pad

poly-time adversary

31 of 40

Commitments from PRFS

32 of 40

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

…

33 of 40

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

…

34 of 40

Commitment schemes

Example use: bids in auction can be confidentially submitted using a�commitment scheme, and only opened when everyone has submitted their bids.

Commitment schemes are fundamental building block in cryptography. They can be used to construct:

coin-flipping protocols
zero-knowledge proofs
signature schemes
secure multiparty computation protocols (recent work by BCKM ‘21, GLSV ‘21).

Commitment schemes can be built from PRGs.

35 of 40

Naor Commitment Scheme

Committer

Receiver

Commitment Phase:

Opening Phase:

Committer

Receiver

36 of 40

QNaor Commitment Scheme

Committer

Receiver

Commitment Phase:

Opening Phase:

Committer

Receiver

= PRFS generator with

37 of 40

QNaor Commitment Scheme

Committer

Receiver

Commitment Phase:

Opening Phase:

Committer

Receiver

= PRFS generator with

38 of 40

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).

39 of 40

Summary

Quantum information is revising our understanding of what minimal assumptions are needed for cryptography.

Pseudorandom states (defined by Ji, Liu, Song) are novel computational objects that appear to be more basic than one-way functions, but wasn’t obvious how to use PRS for crypto.

By introducing concept of pseudorandom function-like states (PRFS), we build paradigmatic cryptographic primitives (e.g., encryption, commitment schemes) from PRS.

40 of 40

Open Questions

What are other cryptographic uses of pseudorandom states?��- OWFs imply digital signatures; can build them using PRS instead?

Is there a “public-key” notion of pseudorandom states? Would it be sufficient to construct public-key quantum money?

What other notions of “quantum pseudorandomness” are there?

Thank You!