# 量子密钥分发

> 版权所有 (c) 2021 百度量子计算研究所，保留所有权利。

## 背景介绍

本节我们将介绍量子密钥分发（Quantum Key Distribution），并以最经典的量子密钥分发协议——BB84 协议<sup>\[1]</sup>为例，介绍量子密钥分发的基本原理。在学习具体协议之前，我们不妨先来简单了解一下什么是密钥分发，以及为什么量子密钥分发具有如此重要的意义。

在现代通信中，目前被大量使用的加密方法是对称加密：即通信双方使用同样的一个密钥 $$k$$ ，对需要加密的消息 $$m$$ 进行加/解密。密钥分发最基本的含义就是将密钥 $$k$$ 分发给通讯双方，以供他们使用。优秀的对称加密算法（如 AES）可以保证窃听者即使窃听到了大量加密后的密文，也无法获取足够的关于密钥 $$k$$ 的信息，来破解被加密的消息 $$m$$ 。但显然，任何算法都不能保证密钥 $$k$$ 本身不在使用前就被泄露。因此，密钥分发成为了密码学中独立于加密算法设计的新任务。

密码学中的非对称加密算法常被用于实现密钥分发。在非对称加密中，用户 Alice 生成并保管一个私钥 $$k\_s$$ ，并广播一个公钥 $$k\_p$$ 。任何人都可以用 Alice 的公钥 $$k\_p$$ 加密消息 $$m$$ ，但非对称加密算法保证只有持有私钥 $$k\_s$$ 的用户 Alice 可以解密得到该消息。具体来说，用非对称加密来进行密钥分发的流程是：用户 Alice 生成并保管一个私钥 $$k\_s$$ ，并向用户 Bob 发送公钥 $$k\_p$$ ；用户 Bob 使用公钥 $$k\_p$$ 加密需要分发的密钥 $$k$$ ，随后用户 Alice 用私钥 $$k\_s$$ 解密得到 $$k$$ 。在整个流程中密钥 $$k$$ 只在公共信道中出现了一次，并且加密算法保证了任何公共信道上的窃听者都不能得到密钥 $$k$$ 。因此，非对称加密成功实现了密钥分发的功能。但是相对地，非对称加密也会比对称加密算法消耗更多的时间，因此非对称加密一般只用来做密钥分发，不用来直接进行加密通信。

目前最常用的非对称加密算法是基于大数分解问题的困难性的 RSA 算法。但是随着秀尔算法 的出现，量子计算机能高效地进行大数分解，导致 RSA 算法的安全性受到威胁。有趣的是，量子力学给密钥分发带来了挑战的同时也带来了新的机遇——量子不可克隆性（未知量子态无法被复制）禁止了窃听者对未知量子态的复制，而窃听者对量子态测量所带来的坍缩现象使窃听检测成为可能。量子密钥分发就是基于这些量子特性设计的全新的密钥分发方式。不同于传统的、基于计算困难性假设的密钥分发协议（如 RSA），量子密钥分发基于量子力学机制，不需要其他额外的假设，因而原则上可实现所谓的“无条件安全”。

下图给出了 BB84 协议的流程概览，展示了 Alice 和 Bob 双方借助经典信道和量子信道完成量子密钥分发任务的场景。其中Eve在中间对经典信道进行窃听，并在量子信道一侧做截获、测量、重发的操作。接下来我们将介绍 BB84 协议的基本原理，随后给出一个完整的 BB84 协议流程。

![BB84 协议流程概览](https://523098360-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FDSRuQAWtUopJaJ476q7i%2Fuploads%2Fgit-blob-cacb84396fe8c8f9d3d02d656139853a4914a3eb%2Fother_qkd-fig-BB84.png?alt=media)

*图 1: BB84 协议流程概览*

## BB84 协议基本原理

BB84 协议会用到如下两组正交基，分别是泡利 $$Z$$ 算符和泡利 $$X$$ 算符的本征态：

$$
\begin{align}
Z\text{-基} &=\left{|0\rangle,|1\rangle\right}, ,\tag{1} \\
X\text{-基} &=\left{|+\rangle, |-\rangle\right}, ,\tag{2}
\end{align}
$$

其中 $$|+\rangle=\frac{|0\rangle+|1\rangle}{\sqrt{2}},\~ |-\rangle=\frac{|0\rangle-|1\rangle}{\sqrt{2}}$$ 。

如果 Alice 希望传输一个经典比特信息 $$b \in {0,1}$$ 给 Bob，她可以先随机选定 $$Z$$ -基或者 $$X$$ -基用于制备量子比特。如果选择了 $$Z$$ -基，就准备以下量子态给 Bob：

$$
|b\rangle=\left{
\begin{array}{rl}
|0\rangle&\text{if }b=0 \\
|1\rangle&\text{if }b=1\\
\end{array}
\right.\tag{3}
$$

如果选择了 $$X$$ -基，就准备以下量子态给 Bob：

$$
\frac{1}{\sqrt{2}}(|0\rangle+(-1)^b|1\rangle)=\left{
\begin{array}{rl}
|+\rangle&\text{if }b=0 \\
\|-\rangle&\text{if }b=1\\
\end{array}
\right.\tag{4}
$$

待 Bob 收到量子比特后，Alice 再公布她选择的基。如果 Bob 用 Alice 公布的基对收到的量子比特进行测量，由于基态之间的正交性，Bob 将以概率 1 得到 Alice 希望传输的经典比特信息 $$b$$ 。举个例子，假设 Alice 想要传递一个经典比特 $$0$$ ，在制备量子态时，她随机选取了 $$X$$ -基，此时 Alice 制备的量子态为 $$|+\rangle$$ 。当 Bob 接收到这个量子态后，Alice 广播告知 Bob 她制备时使用了 $$X$$ -基，于是 Bob 在该基底下对接收的量子态进行测量，得到结果 $$0$$ ，即 Alice 想要传递的信息。

BB84 协议的核心思想在于：如果量子比特在传输过程中被窃听者 Eve 截获，Eve 在不知道 Alice 选择了哪组基的情况下只能随机采用 $$Z$$ -基或者 $$X$$ -基对截获的量子比特进行测量。而一旦 Eve 使用了错误的基，她便只有一半的概率能够得到正确的测量结果。更糟糕的是，一旦 Eve 使用了错误的基，Alice 和 Bob 就很可能发现 Eve 的窃听！

考虑下面这个例子，Alice 现在想要传递一个 7 比特的信息给 Bob：

$$
{\rm bit}\_a = 0101110
$$

为保证 Eve 无法得知此信息，在制备量子比特时，她随机选取了制备基底，此处随机生成如下：

$$
{\rm base}\_a = XXZZXZZ
$$

此时制备的量子比特为：

$$
|+-01-10\rangle
$$

如果没有 Eve，Bob 在收到后可让 Alice 广播告知制备基底，随后 Bob 将采用对应基底进行测量，解码得到经典比特串：

$$
{\rm bit}\_b = 0101110
$$

如果存在 Eve，在她截获传递的量子比特串后，由于不知道制备基底，只能随机选择测量基。此处考虑 Eve 对前 4 位按以下测量基底测量：

$$
{\rm base}\_e = XZZX
$$

注意到此时第 2, 4 位的测量基与制备基不同，故只有第 1, 3 位的测量结果保证正确，而第 2, 4 位仅有 $$1/2$$ 概率得到正确结果。假定此处第 4 位测量错误，则 Eve 得到的比特串为：

$$
{\rm bit}\_e = 0100
$$

在测量后为保证 Bob 不发现量子比特数减少了，Eve 需重新在原有位置制备量子态，而她能做到的也仅有以她的测量基与测量结果制备对应量子态，故此时 Eve 传递给 Bob 的量子比特串为

$$
|+10+-10\rangle
$$

同样的，Bob 在收到后让 Alice 广播告知制备基底，随后 Bob 将采用对应基底进行测量。注意到，由于此时第 2, 4 位量子比特并非对应制备基底的本征态，故很有可能测得错误结果。假如此两位测量结果均错误，将解码得到经典比特：

$$
{\rm bit}\_b = 0000110
$$

因此，如果事后 Alice 和 Bob 核对传输的比特串 $${\rm bit}\_a$$ 和 $${\rm bit}\_b$$ 就很可能使 Eve 的窃听暴露。

注： 为便于读者理解 BB84 协议的核心原理，此处 Bob 在 Alice 告知制备基底后才进行测量。在实际操作中，Bob 将在 Alice 广播基底之前进行测量，以保证 Eve 不可能对 Bob 的测量结果产生干涉，随后根据 Alice 告知的制备基底选取可用比特。相比于告知制备基底再测量的情况，实际操作中仅有约一半的比特可用。

注： 关于事后核对，Alice 将随机挑选比特串中部分位置比特用于核对，并保留余下部分用作密钥分发。故当比特串很长时，Eve 暴露的概率将趋近于 1。

下面我们基于量易伏平台的代码展示上述无窃听者和有窃听者时 Alice 向 Bob 传输信息的过程，推荐读者在本地使用 QCompute SDK 进行模拟实验。

```python
from QCompute import *
from QCompute import Define

# 以下代码用于关闭不必要的输出
Define.Settings.drawCircuitControl = []
Define.Settings.outputInfo = False

def prepare(base, bit):
    """
    根据待传输的比特 bit 和基选择 base 制备量子比特
    此处 base 为数字串：
        base = 0 时用 Z-基
        base = 1 时用 X-基
    """
    # base 和 bit 的长度一致
    assert len(base) == len(bit)  
    n = len(base)
    qubit = []
    qubit_description = ''
    for i in range(n):
        # 当 base = 0 时用 Z-基
        if base[i] == '0':
            if bit[i] == '0':
                q = env.Q[i]
                # 当 bit = 0 时制备 |0>
                qubit.append(q)
                qubit_description += '0'
            else:
                q = env.Q[i]
                X(q)
                # 当 bit = 0 时制备 |1>=X|0>
                qubit.append(q)
                qubit_description += '1'
        # 当 base = 1 时用 X-基
        else:
            if bit[i] == '0':
                q = env.Q[i]
                H(q)
                # 当 bit = 0 时制备 |+>=H|0>
                qubit.append(q)
                qubit_description += '+'
            else:
                q = env.Q[i]
                X(q)
                H(q)
                # 当 bit = 0 时制备 |->=HX|0>
                qubit.append(q)
                qubit_description += '-'
    return qubit, '|' + qubit_description + '>'


def measure(base, qubit):
    """
    根据收到的量子比特 qubit 和基选择 base 得到测量结果
    由于量易伏对测量结果采用大端在前的标记方法，此处输出翻转--通过bit[::-1]
    """
    # base 和 qubit 的长度一致
    assert len(base) == len(qubit)  
    n = len(base)
    for i in range(n):
        # 当 base = 1 时从 X-基转到 Z-基
        if base[i] == '1':
            H(qubit[i])
    MeasureZ(qubit, range(n))
    taskResult = env.commit(shots=SHOT, fetchMeasure=True)
    bit = max(taskResult['counts'], key=taskResult['counts'].get)
    # QCompute 默认从最后一位开始测量，因此输出需要反向
    return bit[::-1]


SHOT = 1024

# Alice 使用 XXZZXZZ-基传输经典比特 0101110 给 Bob
bit_a = '0101110'
base_a = '1100100'

# Alice 制备量子比特
# 生成环境
env = QEnv()
# 选择后端
seeds = '-s 68652'
env.backend(BackendName.LocalBaiduSim2, seeds)
qubit_a, qubit_description_a = prepare(base_a, bit_a)
print("Alice 制备的量子比特：", qubit_description_a)

# Bob 收到量子比特
qubit_b = qubit_a

# Bob 使用和 Alice 相同的基
base_b = base_a

# Bob 对量子比特进行测量得到 Alice 传输的经典比特 0
bit_b = measure(base_b, qubit_b)
print("Bob 得到的经典比特：", bit_b)

```

代码输出：

```python
Alice 制备的量子比特： |+-01-10>
Bob 得到的经典比特： 0101110

```

接下来的代码展示了有窃听者时的情况：

```python
# Alice 使用 XXZZXZZ-基传输经典比特 0101110 给 Bob
# Alice 制备的量子比特： |+-01-10>
bit_a = '0101110'
base_a = '1100100'

# Alice 制备量子比特
# 生成环境
env = QEnv()
# 选择后端
seeds = '-s 6843520'
env.backend(BackendName.LocalBaiduSim2, seeds)
qubit_a, qubit_description_a = prepare(base_a, bit_a)
print("Alice 制备的量子比特：", qubit_description_a)

# Eve 截获量子比特
qubit_e = qubit_a

# Eve 对前 4 位按 XZZX 基底测量：
base_e = [1001]
base_e = ''.join(map(str, base_e))

# Eve 得到的测量结果
bit_e = measure(base_e, qubit_e[:4])

# 由于 Eve 使用了 XZZX 基的测量，导致前四位量子比特坍缩到 |+10+> 态
# 生成环境
env = QEnv()
# 选择后端
seeds = '-s 9968'
env.backend(BackendName.LocalBaiduSim2, seeds)
qubit_e_prime, qubit_description_e = prepare(base_e, bit_e)
print("Eve 测量导致量子比特坍缩到：", qubit_description_e)

# Eve 重新制备量子态发送给 Bob
# 后 3 个量子比特不变
bit_e = bit_e + bit_a[4:]
base_e = base_e + base_a[4:]
# 生成环境
env = QEnv()
# 选择后端
seeds = '-s 65079'
env.backend(BackendName.LocalBaiduSim2, seeds)
qubit_e, qubit_description_e = prepare(base_e, bit_e)

# Bob 之后收到了从 Eve 发来的量子比特
qubit_b = qubit_e

# Bob 使用和 Alice 相同的基
base_b = base_a

# Bob 对量子比特进行测量，以一半的概率得到正确的经典比特 0，以一半的概率得到错误的经典比特 1
bit_b = measure(base_b, qubit_b)
print("Bob 得到的经典比特：", bit_b)

```

代码输出：

```python
Alice 制备的量子比特： |+-01-10>
Eve 测量导致量子比特坍缩到： |+10+>
Bob 得到的经典比特： 0000110

```

下一小节我们将更具体地展示 BB84 协议的完整流程。

## BB84 协议流程

在这一节，我们展示 BB84 协议的具体步骤及细节，并基于混合语言编程演示传输 20 比特的例子。

步骤1： Alice 随机产生一个长度为 $$n=20$$ 的随机比特串 $${\rm bit}\_a$$ 用作待分发的密钥。同时 Alice 随机产生另一个同样长度的比特串 $${\rm base}\_a$$ 用来选择使用哪组正交基。

```python
import random

# bit_a 和 base_a 的长度都为 20
n_bit = 20
n_base = 20

# Alice 随机生成 bit_a 和 base_a
random.seed(2021)
base_a = [random.randint(0, 1) for _ in range(n_base)]
base_a = ''.join(map(str, base_a))
bit_a = [random.randint(0, 1) for _ in range(n_bit)]
bit_a = ''.join(map(str, bit_a))
base_description_a = ''
for base in base_a:
    if base == '0':
        base_description_a += 'Z'
    else:
        base_description_a += 'X'
print("Alice 传输的比特串：", bit_a)
print("Alice 选择的制备基：", base_description_a)

```

代码输出：

```python
Alice 传输的比特串： 01111100011100111010
Alice 选择的制备基： XXZZXXZXXXXZZZZZXZXZ

```

步骤2： Alice 根据 $${\rm bit}\_a$$ 和 $${\rm base}\_a$$ 生成一个长度同样为 $$n$$ 的量子比特串并发送给 Bob。

```python
# Alice 制备量子比特
# 生成环境
env = QEnv()
# 选择后端
seeds = '-s 68678'
env.backend(BackendName.LocalBaiduSim2, seeds)
qubit_a, qubit_description_a = prepare(base_a, bit_a)
print("Alice 制备的量子比特：", qubit_description_a)

```

代码输出：

```python
Alice 制备的量子比特： |+-11--0++--10011-0-0>

```

步骤3： Eve 截获了这些量子比特，并随机以 $$Z$$ -基或者 $$X$$ -基对部分截获的量子比特进行测量。为了不让 Alice 和 Bob 发现异常，她必须依据自己的测量结果重新制备量子态发送给 Bob。在这个例子里，我们假定 Eve 对截获的前 10 个量子比特进行测量。

```python
# Eve 截获量子比特
qubit_e = qubit_a

# Eve 随机测量截获的 n/2 个量子比特，不妨设 Eve 恰好测量了截获的前 n/2 个量子比特
# Eve 的测量基
random.seed(6)
measure_num_e = int(n_base/2)
base_e = [random.randint(0, 1) for _ in range(measure_num_e)]
base_e = ''.join(map(str, base_e))
base_description_e = ''
for base in base_e:
    if base == '0':
        base_description_e += 'Z'
    else:
        base_description_e += 'X'
# Eve 根据自己的测量基测量前 n 个量子比特
bit_e = measure(base_e, qubit_e[:measure_num_e])
print("Eve 选择的测量基：", base_description_e)
print("Eve 测量得到的比特串：", bit_e)


# Eve 重新制备量子态发送给 Bob
# 前 n/4 个量子比特可能发生了坍缩，后 3n/4 个量子比特不变
bit_e = bit_e + bit_a[measure_num_e:]
base_e = base_e + base_a[measure_num_e:]
# 生成环境
env = QEnv()
# 选择后端
seeds = '-s 65057'
env.backend(BackendName.LocalBaiduSim2, seeds)
qubit_e, qubit_description_e = prepare(base_e, bit_e)
print("Eve 制备的量子比特：", qubit_description_e)

```

代码输出：

```python
Eve 选择的测量基： ZXXZZZXXXZ
Eve 测量得到的比特串： 1101000000
Eve 制备的量子比特： |1-+100+++0-10011-0-0>

```

步骤4： 在 Bob 收到全部的量子态后，他随机以 $$Z$$ -基或者 $$X$$ -基对收到的量子比特进行测量，测量基的选择记为 $${\rm base}\_b$$ ，测量结果记为 $${\rm bit}\_b$$ 。Bob 保留他的测量结果，并公布他选择的测量基 $${\rm base}\_b$$ 。

```python
# Bob 使用随机的测量基
random.seed(4)
base_b = [random.randint(0, 1) for _ in range(int(n_base))]
base_b = ''.join(map(str, base_b))
base_description_b = ''
for base in base_b:
    if base == '0':
        base_description_b += 'Z'
    else:
        base_description_b += 'X'

# Bob 对收到的量子比特进行测量
qubit_b = qubit_e
bit_b = measure(base_b, qubit_b)
print("Bob 选择的制备基：", base_description_b)
print("Bob 得到的经典比特：", bit_b)

```

代码输出：

```python
Bob 选择的制备基： ZXZXXZZZZXXZZXXZZXZZ
Bob 得到的经典比特： 11001001111100011100

```

步骤5： Alice 也公布她准备量子态时使用的测量基 $${\rm base}\_a$$ 。Alice 和 Bob 只保留测量基相同时传输的比特 $${\rm agree}\_a$$ 和 $${\rm agree}\_b$$ 。如果 Alice 和 Bob 的基都是随机选取的，则在每一位上他们将有一半的概率选择了相同的基，因此他们将保留约一半的传输比特。

```python
# Alice 和 Bob 公开选择的基，比较并决定保留哪些经典比特
agree_a = agree_b = ''
for i in range(len(base_a)):
    if base_a[i] == base_b[i]:
        agree_a += bit_a[i]
        agree_b += bit_b[i]
print("Alice 保留的经典比特：", agree_a)
print("Bob 保留的经典比特：", agree_b)

```

代码输出：

```python
Alice 保留的经典比特： 1110111010
Bob 保留的经典比特： 1010111010

```

步骤6： Alice 和 Bob 在保留的比特串中再随机取出一半（ $${\rm test}\_a$$ 和 $${\rm test}\_b$$ ）用作窃听检测。如果 Alice 和 Bob 用来检测的比特串中有任何一位不同，他们就直接终止协议，扔掉所有之前准备和交换过的比特，并重新执行新的协议直至检测通过；如果通过窃听检测，Alice 和 Bob 各自保留剩下的比特作为共享的密钥 $$k$$ 。

```python
# Alice 和 Bob 随机使用保留的经典比特中的一半来进行窃听检测，不妨设使用前一半
test_a = agree_a[:int(len(agree_a)/2)]
test_b = agree_b[:int(len(agree_b)/2)]
if test_a == test_b:
    print("未检测到窃听")
    k_a = agree_a[int(len(agree_a)/2):]
    k_b = agree_a[int(len(agree_b)/2):]
else:
    print("检测到窃听！")

```

代码输出：

```python
检测到窃听！

```

以上就是一个 BB84 密钥分发协议的完整流程。流程中三方使用过的信息可以总结如下：

| 参与者   | 发送/窃听/接收 到的经典比特      | 测量/制备基               | Alice 和 Bob 核对基后保留的经典比特 | Alice 和 Bob 用来检测的经典比特 |
| ----- | -------------------- | -------------------- | ----------------------- | --------------------- |
| Alice | 01111100011100111010 | XXZZXXZXXXXZZZZZXZXZ | 1110111010              | 11101                 |
| Eve   | 1101000000(对前10个)    | ZXXZZZXXXZ           | 无                       | 无                     |
| Bob   | 11001001111100011100 | ZXZXXZZZZXXZZXXZZXZZ | 1010111010              | 10101                 |

最后我们简单分析一下 BB84 协议的安全性和密钥率。由上述协议流程可知，如果 Eve 对一个量子比特进行了窃听，那么她选择错误的基的概率为 $$1/2$$ 。由于最后 Alice 与 Bob 仅保留相同测量基结果作为有效比特，对此量子比特 Bob 选择了正确的基的概率也为 $$1/2$$ ，且此时 Bob 测量错误的概率也为 $$1/2$$ 。因此，Eve 对一个量子比特进行窃听且不暴露的概率为 $$1-1/8=7/8$$ 。若 Eve 对多个量子比特进行窃听，她不暴露的概率将呈指数级减小。

BB84 协议的密钥率指在没有攻击者 Eve 的情况下，平均每消耗一个量子比特可以分发的密钥比特数。设 Alice 共发送了 $$n$$ 个量子比特，由上述协议流程可知，Bob 有 $$1/2$$ 的概率选择与 Alice 相同的测量基，因此平均 $$n/2$$ 的传输比特可以共同保留。在保留的比特中，如果 Alice 和 Bob 再随机取出一半用作窃听检测，那么最后共享密钥 $$k$$ 的长度为 $$n/4$$ 。因此， BB84 协议的密钥分发效率为 $$(n/4)/(n)=1/4$$ (bit/qubit)。

当然，最后值得一提的是，以上讨论的 BB84 协议只是一个理想的范例。在实验中，还有诸如信道噪音，量子发送和接收器的缺陷等诸多因素需要考虑。实际情况中，为了提高密钥分发效率 Alice 和 Bob 的测量基选取不一定成均匀分布，而且我们往往也只会选取很少的一部分来检测 Eve 的存在，协议中止的条件也有一定的容错率，并不是发现有一位比特出错就抛弃整个协议重来。为了涵盖这些信道噪音和容错率，使得量子密钥分发能真正在现实环境中执行，Alice 和 Bob 最后得到的密钥还需要经过密钥纠错和隐私增强等进一步处理。

在 BB84 协议提出之后，大量相关的实验验证了其可行性。与此同时，各种其他量子密钥分发协议不断被提出，对应协议的安全性分析也在不断完善。

## 参考资料

\[1] Bennett, Charles H., and Gilles Brassard. "Quantum cryptography: Public key distribution and coin tossing." Proceedings of IEEE International Conference on Computers, Systems and Signal Processing, Bangalore, India, (1984): 175-179.

最后更新时间：2021年12月20日