Cryptography: Quantum Key Distribution (QKD)

Quantum key distribution (QKD)

Quantum Key Distribution (QKD) uses quantum carriers to transmit keys over a confidential channel. After sharing the key, Alice and Bob perform a test to detect eavesdropping. If eavesdropping is detected, they discard the key; otherwise, they use it.

QKD security relies on the principle that any quantum measurement leaves a detectable trace, making eavesdropping detectable. Alice and Bob can use a public channel to communicate about the test.

Perfect Secrecy for One-Time Pad Cryptography

Protocols

Cryptography is the art of encrypting messages for secure communication between two parties, traditionally named Alice and Bob, such that an adversary, Eve, cannot decrypt intercepted messages.

Perfect secrecy for one-time pad cryptography

The one-time pad technique, uses identical encoding/decoding keys for secure communication between Alice and Bob. These keys, originally from punched tapes or pads, consist of random bits. Alice encrypts the message by adding the key bit to each message bit, and Bob decrypts by adding the same key bit to the encoded bit.

This method requires prior secure key exchange but allows the encoded message to be sent publicly, as Eve cannot decode it.

Claude Shannon mathematically proved the absolute security of the one-time pad, provided the key is at least as long as the message. If the key is shorter, the cipher becomes vulnerable to cryptanalysis.

The definition of conditional probability (the probability that an event $A$ occur given that $B$ occur) is:

$$P(B \mid A) \;=\;\frac{P(A \cap B)}{P(A)}$$

If two events $A$ and $B$ satisfy:

$$P(A \cap B) = P(A)P(B)$$

then they are independent. Equivalently, for these independent events, using the above:

$$P(B \mid A) = P(B)$$

Shannon’s Perfect Secrecy theorem states that, for a message $M$, a uniformly distributed key $K$ of the same length as $M$, and ciphertext $C = M \oplus K$, we have:

$$P(M = m | C = c) = P(M = m) \quad \forall m, c$$

Therefore, the ciphertext reveals no information about the message and the knowledge of the ciphertext never changes the probability that a given plaintext occurs.

Proof

Let $M$, $K$, $C$ be random variables with $C = M \oplus K$. For any specific $m$ and $c$:

$$P(M = m \mid C = c) = \frac{P(M = m, C = c)}{P(C = c)} = \frac{P(M = m, M \oplus K = c)}{P(C = c)}$$

Since $C = m \oplus K$ must equal $c$, we have $K = m \oplus c$. By uniformity of $K$:

$$P(M = m, K = \, m \oplus c) = P(M = m)\,P(K = \, m \oplus c)$$

If $M$ and $K$ are independent, then

$$P(K = k) = 1/|K|\; \forall k$$ where $|K|$ is the size of the key space. Likewise:

$$P(C = c) = \sum_{m^\prime} P(M = m^\prime)\,P(K = \, m^\prime \oplus c) = \sum_{m^\prime} P(M = m^\prime) \frac{1}{|K|} = \frac{1}{|K|}$$

Substituting:

$$P(M = m \mid C = c) = \frac{P(M = m)\,\frac{1}{|K|}}{\frac{1}{|K|}} = P(M = m).$$

This shows the ciphertext provides no information about the message.

A one-time pad encryption scheme achieves perfect secrecy if and only if:

1. The key is truly random
2. The key is at least as long as the message
3. The key is never reused

Protocols

BB84 protocol

Ekert protocol