Quantum Uncloneability
Anne Broadbent
With many thanks to:
Eric Culf, Rabib Islam, Stacey Jeffery, Martti Karvonen,
Monica Nevins, Sébastien Lord, Arthur Mehta,
Supartha Podder, Hadi Salmasian, Aarthi Sundaram

Extreme Universe colloquium

Kyoto University
November 14 2023

Quantum States Can’t be Copied

Park (1970); Dieks & Wootters-Zurek (1982)

Quantum Information
Can be tasted, but this leaves a mark.

Conventional Information
Can be observed without changing it.

Can be shared, but there is a total of
1 item to be shared.

Can be shared at will.

Cannot be copied.

Can be copied.

Qubits (“quantum states”)
A pure qubit can be in one of the basis states:

It can also be in a superposition,

where.

Systems of qubits are combined with the tensor product:

4

Measurements: qubits ⟶ bits

Measuring a quantum system will not, in general, give acomplete description of the state.
Measurement destroys the quantum state.
5

Transformations
Postulate: quantum evolutions are linear⟹transformations are given by matrix multiplication.
Unitary matrices are the valid quantum transformations, since they
are the transformations that preserve Euclidean norm.
Theorem: U unitary if and only if, where

6

The Quantum No-cloning Theorem“clone”

7The Quantum No-cloning Theorem8Quantum States Can’t be Copied

What isuncloneability?
Aaronson (2009)
Quantum Copy-Protectionand Quantum Money

Park (1970); Dieks & Wootters-Zurek (1982)

What is uncloneability?
What is security?

“Security for an encryption scheme can be defined in terms of a game”

Uncloneable Authenticity

Quantum Money

Wiesner (ca. 1969)

Written in 1968
Published 1983

12

Wiesner’s conjugate coding
Pick basis 𝜃𝜃 ∈ {0,1} .
Pick bit 𝑟𝑟 ∈ {0,1}.
let 𝑟𝑟 𝜃𝜃 = 𝐻𝐻𝜃𝜃 𝑟𝑟

𝜽𝜽𝒓𝒓𝒓𝒓 𝜽𝜽

1011+0001

r=0 : Computational basis : { 0 , 1 }r=1 : Diagonal basis: { + , − )+ =− =1210
1−(0 + 1)(0 − 1)
2
Given a single copy of |𝑟𝑟⟩𝜃𝜃 for random r, 𝜃𝜃:••Can easily verify |𝑟𝑟⟩𝜃𝜃 if r, 𝜃𝜃 are known.

Intuitively: without knowledge of the encoding basis, no third
party can create two quantum states that pass this verification
with high probability.

13For bit-strings 𝜃𝜃 = 𝜃𝜃1 𝜃𝜃2 … 𝜃𝜃𝑛𝑛 , 𝑟𝑟 = 𝑟𝑟1 𝑟𝑟2 … 𝑟𝑟𝑛𝑛 , define|𝑟𝑟⟩𝜃𝜃 = |𝑟𝑟1 ⟩𝜃𝜃1 ⊗ |𝑟𝑟2 ⟩𝜃𝜃2 … ⊗ |𝑟𝑟𝑛𝑛 ⟩𝜃𝜃𝑛𝑛A quantum banknote is |𝑟𝑟⟩𝜃𝜃 for random 𝑟𝑟, 𝜃𝜃 ∈ {0,1}𝑛𝑛 :©AAAS (1992)

14

Wiesner’s security argument

15

Security of Wiesner’s quantum money“attack”

How does the difficulty ofcloning quantum money scalewith the number of qubits, 𝑛𝑛?

Verify(accept)
Verify(accept)

Answer:16

QUANTUM MONEY SINCE WIESNER
Noise-tolerant (‘feasible with current technology’) quantum money• Pastawski, Yao, Jiang, Lukin, Cirac (2012)
Quantum Money with classical verification• Gavinsky (2012)
Public-key quantum money (can be verified by any user)• Farhi, Gosset, Hassidim, Lutomirski, and Shor (2012)• Aaronson and Christiano (2012)• Zhandry (2017)17

Quantum Money =“Uncloneable Authenticity”

Quantum money does not encode any data;
Can the no-cloning principle be used to secure information?

1979Charles
Bennett
Physicist
IBM, USA

GillesBrassard
Computer
Scientist
Universitéde Montréal,Canada19

CONJUGATE CODING
GOES BIG TIME

“BB84 quantum key distribution”
20• BB84 uses conjugate coding in order todetect eavesdropping.
– No eavesdropping detected → shared
key is secret.
– Impossible to achieve with classicalinformation alone• In what other areas of cryptography could quantum
information provide a qualitative advantage?

28

Quantum Encodings for Classical Messages

1. Certified Deletion (Broadbent, Islam 2020)
2. Unclonable Encryption (Broadbent, Lord 2020)

Certified Deletion
A “physical” type of encryption:

Alice inserts a message
into a safe, closes it andsends it to Bob.

Bob decides• return the closed safe before thecombination is revealed as a proof thatmessage was not read
XOR
• Keep the safe and when the combination
is available, open & read the contents

Can we achieve this in a digital world?

Can we achieve this in a digital world?
No!
Proof by contradiction…

Bob can :• Convince Alice that he did not read the message(use copy #1)
AND• Using combination, open & read the content (use copy #2)

Quantum Encryption with
Certified Deletion
Quantum mechanics enables the best of thephysical and digital worlds:• Encoding (encrypting) a classical message
into a quantum state• Bob can prove that he deleted the message
by sending Alice a classical string

Application:

Basic certified deletion scheme by example:𝜃𝜃 random𝜽𝜽0101𝑟𝑟 random

𝑟𝑟

01100

−1+

Wiesner encoding

𝑟𝑟𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 : substring of 𝑟𝑟 where 𝜃𝜃 = 0

𝑟𝑟𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑 : substring of 𝑟𝑟 where 𝜃𝜃 = 1𝑟𝑟 𝜃𝜃𝑟𝑟𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐
𝑟𝑟𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑0• To encrypt 𝑚𝑚 ∈ 0,1 2 , send 𝑟𝑟 𝜃𝜃 , 𝑚𝑚 ⊕ 𝑟𝑟𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐

110• To delete the message, measure all qubits in diagonal basis;• honest behaviour obtains 𝑦𝑦 =∗ 1 ∗ 0 .
• To verify the deletion, check that the 𝜃𝜃 = 1 positions of 𝑑𝑑 equal 𝑟𝑟𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑 .

• To decrypt using key 𝜃𝜃, measure qubits in position where 𝜃𝜃 = 0, to get 𝑟𝑟𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 , then use
𝑚𝑚 ⊕ 𝑟𝑟𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 to compute 𝑚𝑚.

Proof intuition
𝜽𝜽

01010110𝑟𝑟 𝜃𝜃

0−1+𝑟𝑟𝑟𝑟𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐
𝑟𝑟𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑

0110

As the probability of predicting 𝑟𝑟𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑 increases(i.e. adversary produces convincing “proof ofdeletion”)
1
𝐻𝐻 𝑋𝑋 + 𝐻𝐻 𝑍𝑍 ≥ log𝑐𝑐

The probability of guessing 𝑟𝑟𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 decreases(i.e. adversary is unable to decrypt, even giventhe key)34
Maassen & Uffink, 1988More on certified deletion• Device-independent– Kundu & Tan 2020

• Re-usable encryption key; classicalcommunication– Hiroka, Morimae, Nishimaki & Yamakawa 2021

• For fully homomorphic encryption– Poremba 2022

• Commitments and zero-knowledge– Hiroka, Morimae, Nishimaki, & Yamakawa 2022

Unclonable Information

Example 2: Unclonable Encryption

When encryption is classical:

Classical ciphertexts can be copied, hence
it is always possible for multiple
adversaries to perfectly decrypt, given 𝑘𝑘.
37

Uncloneable Encryption Security Game

Optimal Security:
Wiesner-encoding based scheme: [Broadbent, Lord 2020]38

Uncloneable Encryption-application

1.
2.
3.

Alice uses uncloneable encryption and distributes an encrypted movie
ahead of the movie release date.
The day of release, she reveals the key.
Thanks to uncloneable encryption, she is sure that at most one recipient* candecrypt the movie.

*assuming no communication after key reveal39Uncloneable Encryption Scheme + Security

To encrypt 𝑚𝑚 ∈ {0,1}𝑛𝑛 ,Prepare |𝑟𝑟⟩𝜃𝜃 for random𝑟𝑟, 𝜃𝜃 ∈ {0,1}𝑛𝑛

How well can Boband Charlie
simultaneously
guess m?

|𝑟𝑟⟩𝜃𝜃 , 𝑚𝑚 ⊕ 𝑟𝑟40

𝜃𝜃
Measures qubits in a random basis𝜃𝜃 ∈ {0,1}𝑛𝑛 to obtain r.
AB

How well can Bob andCharlie simultaneously
guess r?

C𝜌𝜌𝐴𝐴𝐴𝐴𝐴𝐴𝜃𝜃

Optimal winning probability:41

Uncloneable Bit Security Game𝑚𝑚 ∈𝑅𝑅 {0,1}𝑚𝑚1𝑚𝑚2

Open Question: does there exist a scheme Enc with:

Important step towards Unclonable Indistinguishability(see Ananth, Kaleoglu, Li, Liu & Zhandry 2022)
42Unclonable Functionality

Quantum Copy-Protection:
Unclonable Software

What is quantum copy protection?

𝑓𝑓𝑥𝑥

𝑓𝑓(𝑥𝑥)

Average Correctness:
Up to some error term 𝜂𝜂, outcome
is correct in expectation overchoice of 𝑥𝑥.

Honest-user Copy Protection
What is 𝑓𝑓

𝑥𝑥1 ?

0𝑓𝑓

1
What is 𝑓𝑓 (𝑥𝑥2 )?

Results on Quantum Copy Protection
Aaronson 2009:• All functions (not learnable)• Assumes a quantum oracle
Aaronson, Liu, Liu, Zhandry, Zhang 2020:• All functions (not learnable)• Assumes a classical oracle
Coladangelo, Majenz, Poremba 2020:• Point functions• Assumes a quantum random oracle
Broadbent, Jeffery, Lord, Podder, Sundaram 2021:• Point Functions• Restricted Class of Adversaries• “Honest-Malicious”• No other assumptions

Conclusion

Quantum Unclonability is inspired by thephysical world

What else can we make uncloneable?