量力学的量子力学（家庭版）： 量子密钥分发

在上一篇文章量力学的量子力学（家庭版）：非局域游戏中，我们用通俗的语言为大家介绍过了非局域游戏。在这里我们就以3×3魔方游戏为例，为大家介绍如何通过非局域游戏构造一个量子密钥分发协议。在当今的密码学领域，有一句名言：“密码学家很少能睡好，他们的职业生涯建立在有关计算复杂度的假设上，这些假设可能第二天早上起来就轰然倒塌。”然而，研究量子密钥分发协议的密码学家除外，因为它是据我所知少数可以不依赖计算复杂度的假设就可以保证安全的协议——这样的安全性是我们最希望得到的，因为它只依赖于物理定律的正确性，而不依赖于某些不知真假的假设。同时，它也是量子信息领域最接近商用化的协议了，目前已经有商业上较为成熟的量子密钥分发的硬件和软件——也许明天你就能从华为买到这些设备了！

那量子密钥分发能够解决什么问题呢？先举个例子，大家小时候都看过《潜伏》吧？每次余则成从电台上接受指令的时候，他都是先从电台上听到一串数字，之后再利用一本书来将这串数字翻译成一段话。在密码学里，这串数字就是密文，这段话就是明文，这本书就是密码本，上面记载着密钥。只要有了密码本，我们就可以在密文和明文之间来回翻译。然而，一定长度的密码本只能安全地将相同长度的明文加密为密文——如果用很短的密码本加密很长的明文，那得到的密文就非常的不安全。

量子信息领域的明日之星Renato Renner教授曾经在课上讲过一个笑话：美苏冷战期间，苏联驻美国大使馆曾经从苏联空运了一架飞机的磁带到美国，这些磁带就记录着苏联情报人员需要的密码本——如果这些密码本只被使用一次，那没有人能破译苏联的秘密。然而，美国情报人员很快就发现他们同行的愚蠢之处——这些苏联情报人员很快就把这些密码本用过了一遍，然而他们懒得再从国内运磁带过来了，于是他们又接着用了这些密码本一遍又一遍。很快他们的密码本就被猜的差不多了，他们的机密情报也很快就被破译干净了。

量子密钥分发就可以精确的解决密码本长度过短这个痛点。具体来说，量子密钥分发协议可以安全的在两方之间建立共享的随机数序列，同时保证没有任何第三方能够通过窃听猜到这串随机数序列。这串随机数序列可以被用作密码本上的密钥。通俗的讲，量子密钥分发协议可以通过远程通信手段无中生有地创造出来密码本——大家就再也不需要用飞机运送记录着密码本的磁带啦！

那量子密钥分发是怎么实现的呢？我们这里将不介绍最先提出的量子密钥分发协议，比如BB84协议和EK91协议，而介绍基于非局域游戏的设备无关的量子密钥分发协议。这里我们回忆一下上回书说到的双方的3×3魔方游戏。在包含张三和李四双方的3×3游戏中，我们要面对张三和李四两个神棍。我们会要求张三在魔方中的第一列，第二列或者第三列填入或为0或为1的数字，要求李四在魔方中的第一行，第二行或者第三行填入或为0或为1的数字。我们额外要求每一列有奇数个1，每一行有偶数个1。张三和李四的获胜条件是，他们填入的行和填入的列交叉处的数字相同。经典科技只能让张三和李四获胜的概率为89%，但量子科技可以让张三和李四获胜的概率为100%。现在，我们不再考验张三和李四是否拥有量子科技，转而将张三和李四视为进行加密通讯的两个好人，他们用量子科技各自产生随机数，并且他们两方产生的随机数必须相同。张三和李四就可以直接使用他们在非局域游戏中输出的行与列交叉处的数字。因为在非局域游戏中，张三和李四的获胜概率为100%，所以他们产生的随机数必然是相同的。这样，通过这种非局域游戏，张三和李四得到了一列共享的随机数。

那这串共享的随机数是否有可能泄露给窃听者呢？答案是会泄露一些，但不会全部泄露。这里我们回忆一下上回书说到的三方的3×3魔方游戏。在包含张三、李四和王二麻子三方的3×3游戏中，我们对张三和李四的要求和之前的那个双方的3×3游戏完全一样——也就是说，我们要求张三（李四）往魔方里填某一列（某一行），并且要求魔方中的每一列（每一行）有奇数个（偶数个）1；同时，我们要求王二麻子给出张三填入的那列和李四填入的那行交叉的那个位置的数。张三、李四和王二麻子获胜的条件是，张三、李四和王二麻子能够一致给出一个相同的数，填在张三填的列和李四填的行的交叉位置。经典科技和量子科技都只能让张三、李四和王二麻子获胜的概率为89%。同样，现在，我们不再考验张三、李四和王二麻子是否拥有量子科技。我们将张三和李四视为进行加密通讯的两个好人，王二麻子视为窃听者，我们要求张三和李四两个好人用量子科技产生随机数，并且张三和李四产生的随机数必须相同；王二麻子这个窃听者也用量子科技进行窃听，并且王二麻子能猜中张三和李四产生的随机数。这样，张三和李四就可以直接使用他们在非局域游戏中输出的行与列交叉处的数字作为他们产生的随机数，而王二麻子就可以用非局域游戏中同样的方法猜交叉位置的那个数。在这种情况下，三个人给出相同数字的概率只有89%。

下面，我们考虑张三和李四这两个好人之间进行了很多轮魔方游戏，并且他们不知道是否有王二麻子这个窃听者也参与了这些轮魔方游戏。于是他们将从这些魔方游戏得到的随机数序列挑一些数字出来进行一下比对。这时候我们就需要分情况讨论：如果张三和李四的数字相同，那么这些魔方游戏既可能是双方的，也可能是三方的，但即使这魔方游戏是三方的，王二麻子猜中张三和李四数字的概率也只有89%，平均9个数字有1个数字猜不中，那张三和李四就可以通过简单的操作，用这9个王二麻子可能猜中一些的数字算出来1个王二麻子很难猜中的数字，然后张三和李四这两个好人就可以用这个数字作为他们安全的共享随机数；如果张三和李四的数字不同，那么张三和李四就可以立刻断定，他们并没有在进行双方的魔方游戏，一定有窃听者在偷听，需要另择良辰吉日，无人偷听的时候，再进行通讯！ 综上所述，如果张三和李四没有发现窃听者，那他们就可以用剩下的随机数创建安全的共享随机数序列。这些随机数序列就可以作为密码本上的密钥了！

注释：

（设备无关的）量子密钥分发，(device-independent) quantum key distribution

参考文献：

Joe Kilian. "Founding crytpography on oblivious transfer." Proceedings of the twentieth annual ACM symposium on Theory of computing. 1988.

Renato Renner. "Security of quantum key distribution." International Journal of Quantum Information 6.01 (2008): 1-127.