Key Distribution

Goal: agree on a uniformly random secret key

. . .

Key Distribution

Once Alice and Bob have agreed on a secret key:

s = 01011

s = 01011

m = 11100

=

Key Distribution

s = 01011

s = 01011

m = 11100

= 1

Once Alice and Bob have agreed on a secret key:

Key Distribution

s = 01011

s = 01011

m = 11100

= 10

Once Alice and Bob have agreed on a secret key:

Key Distribution

s = 01011

s = 01011

m = 11100

= 101

Once Alice and Bob have agreed on a secret key:

Key Distribution

s = 01011

s = 01011

m = 11100

= 1011

Once Alice and Bob have agreed on a secret key:

Key Distribution

s = 01011

s = 01011

m = 11100

= 10111

Once Alice and Bob have agreed on a secret key:

Key Distribution

s = 01011

s = 01011

m = 11100

c = 10111

c = 10111

= 10100

= 10111

For all m, this ciphertext is uniformly distributed from the point of view of an eavesdropper who doesn’t know s.

(i.e. when s is uniformly random)

So, IF there were a way for Alice and Bob to perform “key distribution” (i.e. agree on a uniformly random secret key only known by the two of them), then they would be able to communicate with “unconditional” security!

Once Alice and Bob have agreed on a secret key:

Key Distribution

s = 01011

s = 01011

m = 11100

c = 10111

c = 10111

= 10100

= 10111

For all m, this ciphertext is uniformly distributed from the point of view of an eavesdropper who doesn’t know s.

(i.e. when s is uniformly random)

So, IF there were a way for Alice and Bob to perform “key distribution” (i.e. agree on a uniformly random secret key only known by the two of them), then they would be able to communicate with “unconditional” security!

Means that security holds no matter how much computational power an eavesdropper has

Once Alice and Bob have agreed on a secret key:

Key Distribution

Goal: agree on a uniformly random secret key

Key distribution with unconditional security is impossible classically.

. . .

Key Distribution

0

Key distribution with unconditional security is impossible classically.

Goal: agree on a uniformly random secret key

Key Distribution

0

Key distribution with unconditional security is impossible classically.

Goal: agree on a uniformly random secret key

Key Distribution

0

0

Key distribution with unconditional security is impossible classically.

Goal: agree on a uniformly random secret key

Key Distribution

0

0

1

Key distribution with unconditional security is impossible classically.

Goal: agree on a uniformly random secret key

Key Distribution

0

0

1

1

Key distribution with unconditional security is impossible classically.

Goal: agree on a uniformly random secret key

Key Distribution

0

0

1

1

1

Key distribution with unconditional security is impossible classically.

Goal: agree on a uniformly random secret key

Key Distribution

0

0

1

1

1

1

Classically Eve can ”read” the public communication without disturbing it.

Key distribution with unconditional security is impossible classically.

Goal: agree on a uniformly random secret key

Quantum Key Distribution

Goal: agree on a uniformly random secret key

Quantum Key Distribution

Goal: agree on a uniformly random secret key

Quantum Key Distribution

Goal: agree on a uniformly random secret key

Quantum Key Distribution

Goal: agree on a uniformly random secret key

“

“

Quantum Key Distribution

Goal: agree on a uniformly random secret key

Is it or ?

Quantum Key Distribution

If Eve measures in the wrong basis,

she disturbs the state!

Key distribution with unconditional security is possible quantumly.

[Bennett, Brassard ‘84]

Alice and Bob can leverage this idea to detect eavesdropping!

Goal: agree on a uniformly random secret key

“

“

“BB84”

The BB84 protocol for key distribution

The BB84 protocol for key distribution

The BB84 protocol for key distribution

H C C H C H H C H C

0 1 0 0 1 1 0 0 1 0

The BB84 protocol for key distribution

H C C H C H H C H C

0 1 0 0 1 1 0 0 1 0

The BB84 protocol for key distribution

H C C H C H H C H C

0 1 0 0 1 1 0 0 1 0

The BB84 protocol for key distribution

H C C H C H H C H C

0 1 0 0 1 1 0 0 1 0

H C H C C H C C C C

0 1 1 0 1 1 0 0 1 0

The BB84 protocol for key distribution

H C C H C H H C H C

0 1 0 0 1 1 0 0 1 0

H C H C C H C C C C

0 1 1 0 1 1 0 0 1 0

Consistency check:

The BB84 protocol for key distribution

H C C H C H H C H C

0 1 0 0 1 1 0 0 1 0

H C H C C H C C C C

0 1 1 0 1 1 0 0 1 0

The BB84 protocol for key distribution

H C C H C H H C H C

0 1 0 0 1 1 0 0 1 0

H C H C C H C C C C

0 1 1 0 1 1 0 0 1 0

The BB84 protocol for key distribution

H C C H C H H C H C

0 1 0 0 1 1 0 0 1 0

H C H C C H C C C C

0 1 1 0 1 1 0 0 1 0

1, 5, 8

The BB84 protocol for key distribution

H C C H C H H C H C

0 1 0 0 1 1 0 0 1 0

H C H C C H C C C C

0 1 1 0 1 1 0 0 1 0

1, 5, 8

0 1 0

The BB84 protocol for key distribution

H C C H C H H C H C

0 1 0 0 1 1 0 0 1 0

H C H C C H C C C C

0 1 1 0 1 1 0 0 1 0

1, 5, 8

0 1 0

The BB84 protocol for key distribution

H C C H C H H C H C

0 1 0 0 1 1 0 0 1 0

H C H C C H C C C C

0 1 1 0 1 1 0 0 1 0

1, 5, 8

0 1 0

The BB84 protocol for key distribution

H C C H C H H C H C

0 1 0 0 1 1 0 0 1 0

H C H C C H C C C C

0 1 1 0 1 1 0 0 1 0

1, 5, 8

0 1 0

Use remaining outcomes as the key!