Admin

• Pset5 is out, due December 13, 11:59pm.

​

• Last lecture: this Wednesday. Ask-Me-Anything! Send me your questions before Tuesday night on the Google Form.

​

• Submitters get an extra late day.

Quantum Crypto

Honest parties

Adversaries

Classical

Classical

Quantum

Quantum

Fully Quantum Crypto

Fully quantum crypto

• Fully quantum crypto is about taking advantage of quantum mechanical effects to perform cryptographic tasks:
• Secure key distribution
• Secure multiparty quantum computation
• Device-independent cryptography
• Quantum money
• Quantum homomorphic encryption

​

Quantum key distribution

• This is the flagship application of quantum cryptography so far

​

• Enables secure key generation between two parties where the security is guaranteed by the laws of physics, not based on hardness assumptions.

Quantum key distribution

• Real world implementations exist!
• Companies: idQuantique (Switzerland), MagiQ (USA), SeQureNet (France)

​

• QKD networks
• Cambridge, MA
• Vienna
• Geneva
• Tokyo QKD Network
• China

​

Classical key distribution

Classical key distribution

Authenticated classical channel

Eavesdropper

Classical key distribution

If the adversary has unlimited computational power, since they see all the communication between Alice and Bob, they can “reverse engineer” the most likely secret key agreed upon between Alice and Bob.

​

Classical key distribution is only secure using computational assumptions (e.g. the adversary cannot factor large integers or solve lattice problems).

​

​

Quantum key distribution

Quantum key distribution

Authenticated classical channel

Active eavesdropper

Insecure quantum channel

Quantum key distribution

This goal is possible! First shown by Bennett and Brassard in 1984, who came up with a protocol (known as BB84 protocol).

​

They show that secure key distribution is possible only assuming that

​

• Classical channel is authenticated
• Adversary follows laws of quantum physics

​

In particular, adversary can have unlimited computational power!

Wiesner Conjugate Coding

Standard basis (S):

Diagonal basis (D):

Single qubit example

Single qubit example

Single qubit example

Single qubit example

Single qubit example

Single qubit example

Single qubit example

Quantum key distribution

High level idea: Alice can send Bob many BB84 states.

​

1. Some of them will be used to detect tampering by the adversary (i.e. these are “traps”)

​

• Others will be used to generate the secret key.

​

​

Adversary does not know in advance which qubits will be “traps”, so if it decides to tamper many of them, it will be caught with high probability.

Quantum key distribution

Authenticated classical channel

Quantum key distribution

Authenticated classical channel

Quantum key distribution

Authenticated classical channel

Quantum key distribution

Authenticated classical channel

1. Bob picks random basis sequence: DDDSDSDDSDSDSDSD….

2. Measures his received qubits according to basis sequence

Bob’s raw key: 111101000101010010101

​

3. Bob calls Alice over the phone and they compare their �random basis sequence, and discard the bits where �they don’t match.

​

4. Error detection: Alice and Bob sample a few locations and check that�their raw keys match in those locations. If too many differences�occurred, abort.��5. Otherwise, use privacy amplification to distill a shared secret key.

Quantum key distribution

Authenticated classical channel

Why is this secure?

​

1. No-cloning: the attacker cannot copy�the qubits.

​

• Measurements change the state: if the�attacker tries to obtain information, �it will disturb the qubits, which will�Alice and Bob will detect w.h.p.

Quantum Money

Quantum money

• A scheme to create money that cannot be counterfeited by the laws of physics.
• In principle, all current forms of currency can be copied.
• What if we exploit the No-Cloning theorem?

Quantum money

• [Wiesner ‘77] Conjugate coding (the idea behind the previous QKD scheme), can be used for unclonable money.

​

Giant Database of Banknotes:

​

Serial # (s) Basis Sequence (b_s) Key (k_s)

0000000 SDSDDSDSDDSDS 0100010101001

0000001 DDDSDSSSDDDSS 1110101101010

0000002 SDDDSDSDSDDSD 1010101010100

.

.

.

Quantum money

• Drawbacks of Wiesner’s scheme:
• Giant database problem
• Only the Mint can verify!
• Money can be counterfeited through adaptive attacks

​

• Holy grail: obtain a public-key quantum money scheme
• Banknotes that anyone can verify
• However, banknotes cannot be cloned
• Note: this requires computational assumptions!

Quantum money

• [Aaronson-Christiano 2012]: candidate public-key quantum money scheme.

​

Quantum money

• A major open question in quantum cryptography research: come up with a quantum money scheme that is secure under well-known computational assumptions (e.g. it is hard for quantum computers to solve lattice problems)

​

• The study of quantum money has sparked the era of unclonable cryptography:
• Quantum copy protection – can you encode a program into a quantum state that only a single person can run, but not duplicate?

​

• Tokenized signatures – can you create a quantum state that allows only a single person to sign documents in your name?

​

• Unclonable encryption – encrypt messages into quantum states where, even if everybody has the secret key, only one person is able to decrypt the message.

​

​

Historical note

• Stephen Wiesner was a graduate student in Columbia physics �in the late 1960s and early 1970’s.

​

• Came up with:
• Quantum money
• Superdense coding
• Precursor to oblivious transfer (a fundamental concept in classical cryptography)

​

• His paper on Conjugate Coding was unappreciated for decades, and Wiesner left academia and eventually became a laborer in the desert in Israel.

​

• However, his ideas inspired Bennett and Brassard to invent BB84 protocol and kick off quantum information theory and quantum cryptography.

​

Next time

Ask me anything!

(about quantum)