3.5　密码学新纪元

3.5.1　同态加密技术

同态加密是现代密码学发展的新分支。所谓“同态”，笼统地说是指将密文进行一系列数学运算然后再解密所得的结果，跟对明文进行同样的数学运算所得的结果一致。在现代信息系统中，同态加密有很多的应用场景，简述如下。

• 密文检索：当数据以加密形式存放在服务器端时，如果用户想对数据进行全文检索，一种直接的方式是将数据解密后发给用户，用户利用传统的索引和查表算法进行检索。这种方法既不安全，效率也低。在加密算法具备同态特性时，用户可以将需要检索的关键词加密后发给服务器，服务器直接利用密文进行相应的检索操作，并将密文的检索结果返回给用户。
• 可信云计算：在金融、医疗等行业中，通常需要对大规模的数据进行计算处理。用户在本地无法完成的大型计算分析任务，可以提交给云端进行处理。但是，多数行业的数据都会涉及隐私保护，例如病人的基因数据、商户的账单数据等。在这类场景中，用户可以先将数据进行加密，然后将密文提交到云服务器。云服务器对密文数据进行相关处理运算，将结果返回给用户。在同态的前提下，用户将运算结果解密，也可以得到相同的处理效果。
• 电子投票：在电子投票中，要兼顾公正性和隐秘性。为了保护隐私，每个投票者的投票数据需要先用公钥加密成密文，再提交给统计方。如果统计方只负责计票而并不掌握私钥，那么他只能对各个投票者提交的密文进行叠加计票处理，然后将一系列密文的运算结果反馈给数据的最终审核方。最终审核方已知私钥，可以将密文数据解密。在同态的前提下，上述过程和直接对明文进行计票处理的结果是一致的，不会影响投票的公平性。

从广义上讲，如果函数f作用于明文m后再加密的结果e[ f(m)]等于直接作用于密文的结果f [e(m)]，则称这种效果为同态。当f是加法或乘法时，如果以上过程成立，则表示加密函数e(x)是加同态的或乘同态的。举例来说，RSA加密算法显然是乘同态的，因为其加密函数是密文的幂，两个密文相乘的幂和各自求幂之后再相乘的结果是相等的；此外，前文介绍过的移位密码等线性操作加密函数都是加同态的。如果函数e(x)既满足加同态也满足乘同态，则称它是全同态加密函数。对于全同态加密来说，对于由多个加、乘组合而成的混合运算，也能达到同态的效果。

图3-6形象地展现了同态加密的效果。函数f对数据的处理如同是在看不见的黑箱中对数据进行操作，但是操作人只能进行运算，看不到原始数据，这样既完成了操作的效果，也保障了信息的安全性。

图3-6　同态加密的示意图

同态加密的概念早在20世纪70年代就被提出，但是之后的20余年一直没有非常系统地发展。直到2009年，IBM的密码学专家Craig Gentry的开创性研究才将全同态加密算法研究带入了新的阶段。Gentry在2009年发表的论文“Fully Homomorphic Encryption Using Ideal Latices”中提出了基于“理想格”的全同态加密体质。Gentry采用了一种分步构造的方式，先找到一个部分同态的体制，然后利用类似于叠加公钥、密钥空间映射的方式找到满足要求的全同态体制。Gentry的第一代全同态加密方法的复杂度较高，密钥占用的存储空间过大，因此许多学者在此基础上继续研究性能更优的体制。2010年Dijk等学者将Gentry的研究拓展到了整数的全同态加密体制，类似于我们之前了解过的大整数分解难题，但算法的复杂度还是较高。后续的研究方向集中在如何突破Gentry所提出的基本思路，找到更高效、更能应用于实际的算法。例如，Brakerski等学者在2012年提出了基于Learning With Errors（LWE）困难问题构建的同态加密方案，探索了抛弃理想格难题以及Gentry最初的分布构建框架；Gentry在2013年提出了基于“近似特征向量”构建加密方案的新思路。

虽然目前同态加密算法实现还较为复杂、在应用中还主要处于探索阶段，但随着越来越多学者和专家的关注，它将会不断走向成熟并得到广泛应用。

3.5.2　抗量子攻击密码

由于密钥空间是有限的，只要运算时间足够，最终都能找到真实的密钥并破解算法。目前所讨论的密码算法的安全性都是构建在“计算安全”的基础上的。但是，一些具有前瞻性的科学家已经指出了这其中蕴含的风险。1994年，美国贝尔实验室的学者Shor指出，利用量子计算机能够在短时间内破解大整数分解的数学难题。这预示着，如果量子计算成为现实，大整数分解、离散对数乃至椭圆曲线等数学难题都不再“计算安全”。量子计算距离我们是否遥远？

常见的计算机算法都是基于二进制构建的，因为1比特的单位信息只有0和1两种状态。以二进制为基础的存储和运算，构成了现有算法的基本单元。在前述章节中，我们也以二进制为基础来分析密钥长度、破解复杂度等。在量子计算的世界里，故事完全不同。量子计算基于量子力学的机理，通过量子信息单元的状态变化实现信息的存储和运算。这种情况下，突破原有数字逻辑中0和1的两态限制成为可能。简言之，量子力学中的“量子比特”允许存在叠加态，其效果是将二进制中的每一个比特升维成n个量子比特，从而指数级地增加存储和运算能力。当然，将理论的可能性转化为计算机工程实践，还有很长的路要走。但一如既往地，创新的脚步只会加速。在Shor的研究基础上，人们开始加速推进量子计算机的研发和量子计算的具体算法。2011年，加拿大量子计算公司D-Wave发布了全球第一款商用量子计算机。近年来，全球诸多的研究机构和企业开始了对量子计算机和量子计算方法的探索。2015年，美国NSA正式发布了向抗量子密码算法迁移的通告；2016年8月16号，中国的量子科学实验卫星“墨子号”在酒泉卫星发射中心成功发射。这些标志性事件似乎向全世界宣告量子计算时代即将到来。

在量子计算来势汹汹的背景下，抗量子攻击密码算法的研究得到了许多关注。

抗量子攻击密码主要有四个技术方向，即基于哈希的密码体制、基于编码的密码体制、基于多变量的密码体制和基于格的密码体制。基于哈希的密码体制，其理论基础是哈希函数的碰撞性，该研究方向的主要课题是优化哈希签名的长度和算法的运行速度。基于编码的密码体制的主要框架由McEliece在1978年提出，它的基础是通信领域中常见的信道编码。该方向的基本思路是将明文看作一个编码的输入，然后给明文码字引入随机的错误e，然后将解密的过程建模为译码过程。基于编码的密码体制所遇到的主要挑战是公钥尺寸大、运算复杂度过高，这也是该方向未来的研究重点。基于多变量的密码体制近年来受到的关注较多。这类密码的数学基础是求解有限域上随机的非线性多变量方程组是困难的。这一类体制由于在有限域上进行运算，所以计算复杂度不高，但是随着变量数量的增加，密钥长度也会快速提高。基于格的密码体制是最重要、最有潜力的技术方向之一，目前没有算法可以借助量子计算对其格上的“最短向量”和“最近向量”困难问题进行求解。

诚然，上述密码体质都面临各自的难题和挑战，包括密码系统本身的完善、加/解密算法、签名算法和密钥管理等，也需要不断探索更短的密钥和更高效的计算。幸运的是，世界范围内许多主流的研究和标准化组织，以及知名企业都在积极开展抗量子攻击密码方面的研究探索。国际密码逻辑研究联合会在2006年就举办了以“后量子”时代的密码学为主体的国际会议，覆盖了后续各个主要的学术分支。欧洲电信标准化协会（ETSI）从2013年也开始组织该方向的专题会议和论坛。我国在2016年召开了首届亚洲抗量子密码论坛。预计以后抗量子攻击密码将会得到更多关注，进而实现技术上的快速发展。