3.5.1
同态加密技术

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

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

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

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

同态加密的概念早在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年提出了基于“近似特征向量”构建加密方案的新思路。

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