猫鼠游戏：加密技术如何对付量子计算机？

今年8月的时候，美国国家安全局（NSA）在其网页上更新了一段不起眼的内容，他们计划对现在政府和军方加密数据的方式更新，以期能够阻挡来自量子计算机（quantum computer）的攻击。NSA的发言人表示，量子计算机能够带来更新更强的计算能力，显然现有的安全措施和加密方式无法承受来自这种设备的攻击。如果要严密保护国家系统的安全的话，那么他们需要在这一方向取得显著发展。

量子计算机对于过去的人而言听起来就像是遥远的神话，但现在人们普遍认为在5到30年内它就将成为现实。通过不断探索量子物理的法则，不管是NSA的绝密档案、银行记录还是邮箱密码，这种机器能够解密现在世界上绝大多数“机密”的数据。在意识到这可能的威胁后，密码学家们正在量子计算机大范围使用以前，抓紧开发能够防止量子破译的方案。

现在看来，最可行的方案是基于格的数学方案（mathematics of lattices）。这种方案有效性在于，要在一个拥有几百空间维度的格中找出隐藏的信息非常难，除非你知道那条秘径。

但是去年十月，英国政府通讯总部（GCHQ）的密码专家发表论文指出，即便是最有效的格方案也面临着安全问题。这些发现意味着，在以效率为目标发展了几十年后，这种高效暴露出了安全风险。专家们通过简化他们方案中的格，导致这些方案更容易受到攻击。

基于上面所述的问题，一些密码专家从去年开始都在做实验，看哪些基于格的方案会被量子计算机打破，而哪些至少对于现在而言又是安全的。对于编写密码和破解密码的专家而言，这就是一场猫鼠游戏。当解码员沉默的时候，编码员为了效率会放松方案的安全性，有时候，其结果就是导致安全越过了那条红线。

公开的秘密

在谈论这一话题前，我们需要先对现在的加密方式有一个了解。事实上，当你每次访问以“HTTPS”开头的链接时，你都会发送和接收加密的信息，而这一安全的网络交易方式使用了基于加密技术的公共密钥。这一创造性的发明始于上个世纪70年代，而在此前，密码技术基本就是政府和间谍之间的比赛。通常而言，参与信息传递的人，例如一个人和他的对接人之间如果想要偷偷交流的话，要事先约定一个暗号或者“钥匙”。而公共密钥的技术则可以让任何人给其他人发送一组加密信息，不管是否有人在偷听，只有指定的接受人可以解密，即使参与的人一开始并没有串通好。

在公钥加密技术中，人们通过一些数学技巧来保证数据的安全性，一些数学问题解答起来容易，但是要用逆向工程解码则很难。例如，要计算机计算两个质数的乘积很容易，但是如果给计算机一个数，要它解出组成这个数的质因子，则可能要花费很多时间。在基于质数分解的方案中，这个质数就是某人并不与他人共享的“私钥”。而质数的乘积则是“公钥”，公开分发。当某人用公钥来加密信息时，只有这个拥有私钥的人才能够解密信息。

有两个公钥加密方案自上世纪70年代以来广为应用：一个是基于质因子的RSA方案，另一个是基于离散算法的Diffie-Hellman方案。虽然这两种方案并不是说一定就无法破解，但是没人能够找到高效计算出结果的方法。如果要用计算机将特定长度的公钥进行计算出来，可能要花费数年的时间。因此，这两种方案成了保护互联网信息的力盾。不过它们带来的这份安全，似乎已快来到了终结之时。

Shor的算法

计算机难以短时计算出结果这一神话在1994年被打破，当时AT&T的研究人员Peter Shor提出了一种理论，他认为未来的量子计算机会具有破解算法的能力。

在普通计算机中，信息以比特的形式存储。比特存在两种状态中的一种，即0或者1，而计算机的计算能力与比特数量相称。但是在量子计算机中，数据是用量子位方式存储的，数据存储格式既可以是0也可以是1。由于大量的量子位，使得其中可以存在大量可能的组合形式和可能的个体状态。因此随着量子位数量的上升，量子计算机的计算能力会以指数级的方式增长。

基于此，量子计算机比普通计算机会具有更强的运算能力。然而要开发出其潜力，还必须同时找到一个合适的算法，能够充分利用这种同时存在的状态，即得到正确的解答。80年代量子计算机被提出来以后，超过10多年间都没有什么有用的算法出现，这个领域似乎前途暗淡。

变化发生于1994年，Shor提出了一个量子计算机算法，能够高效破解了质因子和离散算法，也就是说打破了RSA加密方法和Diffie-Hellman密钥交换理论。于是一瞬间，人们对量子计算机的兴趣一下子燃烧了起来。随着Shor的算法揭示出了量子计算机高级的运算能力后，世界范围内的研究人员争相进行研究，试图找出破译的方式。而与之相对应的是，密码编译专家们也在竞相赛跑，提出量子计算机无法攻破的方案。最后他们发现，格似乎是一个不错的选择。

迷失在格里

其实同RSA加密方案类似，理论上来说，计算质数的乘积很容易，但是求解质因子很难，基于格的安全加密方案也取决于，让计算机迷失在一个500维的格中有多难。不同的是，在格方案中，私钥与格点相关，而公钥则与空间中的特定位置有联系。

除了一开始的惊艳，这种加密方案却发展迟缓。80年代的时候，这种方案的公钥都太长，交换数据需要海量的字节空间。为了提高效率，密码学家不得不简化潜在的格。在一个普通的格中，格点是由计算一组向量的线性组合得出。给这些向量分配一个模式，使得算出来的结果简单化，则相关的密钥也更短。但这带来的问题是，简化方案使得人们可以从公钥中推论出私钥，从而破坏这个方案。因而，格对于密码学来说，又成了灾难的代名词。

随着时间的前进，一些密码学专家仍然在不断完善格。1995年的时候，一些专家提出了一种基于“环状”的格，可以产生在任意方向旋转的向量。这个名为NTRU的方案极其高效，甚至比老的RSA和Diffie-Hellman方案更高效。尽管没有证据表明这种方案就是一定安全的，但20年过去了还没有人能破解它，证明某种程度上还是具有安全性的。

格的前景自1997年以后变得明朗起来，IBM的研究人员提出第一种较好的加密方案，这种加密方案名为Learning With Errors（LWE），意即伴随误差学习，由于要找到最近的通用格要很长时间，因而可以抵抗来自量子计算机的攻击。基于理想格下，他们开发出了一个更行之有效的方案。

什么是LWE方案

在2005年，Oded Regev基于LWE问题提出了一种加密方案，他证实这个方案解决起来很难，因而比较安全。这个方案的基本思路是这样的：

首先选择任何一个奇数，并且不要告诉任何一个其他人，这就是你的私钥。然后把它乘上任何一个数，再加上一个小的偶数。重复多次，得到一系列的数，这些数就是你的私钥，然后再把它们告诉别人。

现在，如果有谁想给你发信息，如0或1，首先这个人随机地在你的公钥里选择一半的数，把它们加起来。然后如果要发送0，他们就把数据加起来然后发给你。如果要发送1的话，就把数据加1并发给你。之后你想要解码这段数据的话，只要用你的私钥求出这个和数的商。如果余数是偶数的话，这个信息就是0。如果是奇数，则为1。

再一次，人们似乎又要在安全和效率间进行权衡。鱼和熊掌不可兼得，LWE方案虽然更加通用并且安全性更高，但它的效率较低。研究人员在这个方向上，还在不断探索，之后提出了一些其他方案。

猫鼠游戏

不仅科研人员在开发基于格的加密方案，GCHQ的人员也在做同样的事。他们使用数论开发除了名为Soliloquy的方案，把公钥的大小从一个包含大量数据的矩阵降为仅仅是一个质数。把它量化到格里而言，则是产生一个非常短的矩阵。然而，这种方案的便利也正是其致命之处。

在他们发布的论文中可以看出，他们虽然发明出了这种方案，但是在2013年后又弃用了，原因是他们发现量子攻击可以把这个加密方案攻破。虽然这篇论文只是对攻击草草描绘了一下，但是给人们留下了无限的疑问：其他的格方案是不是也会受到影响？似乎在追求效率的同时，安全的红线随时也被越过。问题是，这条安全的警戒线到底该放在哪里？

GCHQ的团队并没有找出多少细节，而仅仅是觉得有很强的证据证明，这种攻击会被开发出来，因而就推论Soliloquy不适用于现实。于是密码学家们花了差不多一年来了解Soliloquy攻击的范围，此后研究人员发现，这种攻击竟然只需要一台普通的电脑就可以实现。

除了Soliloquy以外，他们的发现还表明，其他基于理想格的方案，构造单独短向量的方法也可以被攻破，而基于一般格的方案，如Ring-LWE和NTRU则不受影响。用研究人员的话来说，似乎想要把这些技术转化成有效的方案还有一些技术上的难题，需要更深的研究。

就安全和效率的对称性而言，密码学家过于倾向效率这一边。在他们给政府和银行等机构寻找最好的抵御量子攻击的时候，Soliloquy这样的攻击迫使他们重新审视过去，回到那些可能没有那么有效率，但是更加稳固的方案。对于一个方案而言，在效率和安全性这两条相反的道路上，还是需要研究人员仔细权衡。