量子安全加密的崎岖之路（下）

RSA不对称加密和Diffie-Hellman密钥交换是互联网的安全之盾，但在Shor揭示了量子计算强大的分解能力之后，安全主宰的未来地位似乎岌岌可危，密码学家开始争相研究量子计算无法破解的加密算法。Quanta的这篇文章讲述了现代版的猫捉老鼠游戏简史。

量子安全加密的崎岖之路（上）

迷失晶格

就像RSA加密的安全是建立在素因子相乘容易分解难的基础上一样，基于晶格的加密法的安全性的基础是，在有着500维度的晶格里面游走极易迷失方向：你先从某个格点开始，然后调整空间坐标，最终走到某个附近的位置。但是在给定500维空间的任意位置情况下，要想找到最近的格点（最近向量问题）极其困难。在晶格加密法中，私钥跟那个格点相关，而公钥则与空间的任意位置相关联。

虽然晶格加密法很有前途，但是它的起步却很慢。1980年代时基于晶格的公钥实在是太长了，长到有数百万字节。为了提高效率，密码学家被迫把晶格简化。在一般的晶格中，格点是通过穷举某些向量集所有可能的线性组合来生成的。给这些向量分配模式可以让晶格简单些，相关的密钥相应也会短一点。但是晶格简化后其遍历也会更容易，导致从公钥推导出私钥变得可能，从而破解成功。这个时候晶格就会变成灾难的同义词。

在别人继续前进的同时，部分密码学家也在继续修补晶格。1995年，Hoffstein、Pipher以及另一位布朗大学的同事Joe Silverman设计了一种基于环状晶格（cyclic）的加密法，这种晶格是用可以朝着任何方向旋转仍然落在另一个格点上的向量生成的。这种名为NTRU的加密法效率极高，甚至比RSA和Diffie-Hellman协议的效率还要高。虽然以NTRU为基础的环状晶格计算机难以浏览未经证明，但20年过去了，还没有人找到破解的办法，这提振了大家对它安全性的信心。

1997年，IBM研究人员Miklós Ajtai和Cynthia Dwork设计出第一种经证明难以破解的晶格加密法，令这种加密法的希望大增。2005年，在此基础上理论计算科学家Oded Regev（现在纽约大学库朗数学学院）证明，只要量子计算机寻找普通晶格的最近点困难，则基于错误学习问题（LWE）的加密法就可以抵御量子计算机破解。LWE效率不高，但Regev、Peikert和 Vadim Lyubashevsky（三人均在IBM瑞士研究院）很快开发出了一种基于“理想”晶格的类似加密法，并且证明了只要底层的理想晶格问题够难，这些更高效的加密法（Ring-LWE）就是安全的。

然而安全和效率之间似乎再次需要权衡，但这两个东西就像鱼和熊掌一样不可得兼。Ring-LWE的安全性比NTRU更有保障，而且通用性也强很多，但是效率却没有那么高。部分研究人员认为自己可以做得更好。自2007年以来，他们一直在考虑基于“主理想晶格（principal ideal lattices）”的加密法，这种晶格由单向量生成，十分类似于{…，-6，-3,0,3,6,9，…}这种由3的倍数构成的整数集。

“他们对现有的效率不满意，他们很贪心，”Regev说。

猫和老鼠

学院派密码学家设计出基于主理想晶格的加密法的同时，GCHQ的那帮人也弄出来了一个。这个东西叫做Soliloquy，它应用了数论的技术来缩短公钥的长度，从一个大数矩阵简化成了一个素数。这相当于用一个很短的向量生成晶格。“不幸的是，用来做这个的东西是它的阿喀琉斯之踵，”GCHQ的一位发言人在邮件中说。

GCHQ研究人员在去年10月发表的一篇论文中披露，自己发明了Soliloquy之后由于发现它可以被量子攻击破解，2013年就放弃了相关工作。不过论文对攻击手段语焉不详，这使得大家对它的机制和哪些加密法也可能受影响存在疑问。这似乎表明，他们在追求效率的过程中已经逾越了红线，不过这条红线到底在哪里呢？

“大家最初认为这种攻击的范围可能会更广，也许会涉及到所有晶格类加密法，”Pipher说。但有的人也质疑这种攻击到底有没有用。

为了确定Soliloquy攻击的范围，密码学家几乎花费了整整一年的时间。结果证明，GCHQ团队并未掌握太多细节，如发言人所述，只是“对可以发起攻击有了充分证据，因此不应该把Soliloquy推荐给实际使用。”在今年3月的一篇论文中，CWI的Regev、Peikert、Cramer以及 Léo Ducas做出了只需要一台普通计算机的攻击部分，而在上周，滑铁卢大学的Jean-François Biasse和Fang Song进一步列举出量化阶梯。

研究发现，除了Soliloquy法以外，其他基于主理想晶格的加密法也是可以破解的，而基于更普通的理想晶格（如Ring-LWE、NTRU）的加密法则不受影响。Cramer 说，这似乎是因为把这种破解技术应用到其他重要的加密法上面时与道路一些技术障碍。

在安全与效率的天平上，密码学家往效率方面倾斜得太多了。是Soliloquy攻击把他们从争相替银行、政府及互联网寻找最好的抗量子攻击手段中拉了回来，让这些人不那么追求效率，更坚定地依靠困难的晶格问题上。

不过目前还无法证明量子计算机找不出绕开晶格的办法。“也有可能所有这些问题其实都很容易解决，” Peikert说：“但就目前所知，可能性不大。”

至于为什么极其高效和完美安全无法得兼，Hoffstein的看法是：“宇宙是一个令人恼火的地方，这只是又一个例证罢了。”