量易简

量子密钥分发

背景介绍

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

在现代通信中，目前被大量使用的加密方法是对称加密：即通信双方使用同样的一个密钥 $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 协议基本原理

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

\begin{matrix} Z -基 & = {| 0 ⟩, | 1 ⟩}, X -基 & = {| + ⟩, | - ⟩}, \\ (1) (2) \end{matrix}

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

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

\begin{matrix} | b ⟩ = {\begin{matrix} | 0 ⟩ & if b = 0 | 1 ⟩ & if b = 1 \end{matrix} \\ (3) \end{matrix}

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

\begin{matrix} \frac{1}{\sqrt{2}} (| 0 ⟩ + (- 1)^{b} | 1 ⟩) = {\begin{matrix} | + ⟩ & if b = 0 | - ⟩ & if b = 1 \end{matrix} \\ (4) \end{matrix}

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

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

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

{b i t}_{a} = 0101110

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

{b a s e}_{a} = X X Z Z X Z Z

此时制备的量子比特为：

| + - 01 - 10 ⟩

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

{b i t}_{b} = 0101110

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

{b a s e}_{e} = X Z Z X

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

{b i t}_{e} = 0100

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

| + 10 + - 10 ⟩

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

{b i t}_{b} = 0000110

因此，如果事后 Alice 和 Bob 核对传输的比特串 ${b i t}_{a}$ 和 ${b i t}_{b}$ 就很可能使 Eve 的窃听暴露。

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

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

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

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)

复制

代码输出：

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

复制

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

# 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)

复制

代码输出：

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

复制

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

BB84 协议流程

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

步骤1： Alice 随机产生一个长度为 $n = 20$ 的随机比特串 ${b i t}_{a}$ 用作待分发的密钥。同时 Alice 随机产生另一个同样长度的比特串 ${b a s e}_{a}$ 用来选择使用哪组正交基。

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)

复制

代码输出：

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

复制

步骤2： Alice 根据 ${b i t}_{a}$ 和 ${b a s e}_{a}$ 生成一个长度同样为 $n$ 的量子比特串并发送给 Bob。

# 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)

复制

代码输出：

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

复制

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

# 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)

复制

代码输出：

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

复制

步骤4： 在 Bob 收到全部的量子态后，他随机以 $Z$ -基或者 $X$ -基对收到的量子比特进行测量，测量基的选择记为 ${b a s e}_{b}$ ，测量结果记为 ${b i t}_{b}$ 。Bob 保留他的测量结果，并公布他选择的测量基 ${b a s e}_{b}$ 。

# 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)

复制

代码输出：

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

复制

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

# 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)

复制

代码输出：

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

复制

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

# 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("检测到窃听！")

复制

代码输出：

检测到窃听！

复制

以上就是一个 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日

背景介绍
BB84 协议基本原理
BB84 协议流程
参考资料