[科普中国]-同态加密

同态加密是基于数学难题的计算复杂性理论的密码学技术。对经过同态加密的数据进行处理得到一个输出，将这一输出进行解密，其结果与用同一方法处理未加密的原始数据得到的输出结果是一样的。

概念随着互联网的发展和云计算概念的诞生，以及人们在密文搜索、电子投票、移动代码和多方计算等方面的需求日益增加，同态加密(Homomorphic Encryption)变得更加重要。同态加密是一类具有特殊自然属性的加密方法，此概念是Rivest等人在20世纪70年代首先提出的，与一般加密算法相比，同态加密除了能实现基本的加密操作之外，还能实现密文间的多种计算功能，即先计算后解密可等价于先解密后计算。这个特性对于保护信息的安全具有重要意义，利用同态加密技术可以先对多个密文进行计算之后再解密，不必对每一个密文解密而花费高昂的计算代价；利用同态加密技术可以实现无密钥方对密文的计算，密文计算无须经过密钥方，既可以减少通信代价，又可以转移计算任务，由此可平衡各方的计算代价；利用同态加密技术可以实现让解密方只能获知最后的结果，而无法获得每一个密文的消息，可以提高信息的安全性。正是由于同态加密技术在计算复杂性、通信复杂性与安全性上的优势，越来越多的研究力量投入到其理论和应用的探索中。近年来，云计算受到广泛关注，而它在实现中遇到的问题之一即是如何保证数据的私密性，同态加密可以在一定程度上解决这个技术难题。

本质上，同态加密是指这样一种加密函数，对明文进行环上的加法和乘法运算再加密，与加密后对密文进行相应的运算，结果是等价的。由于这个良好的性质，人们可以委托第三方对数据进行处理而不泄露信息。具有同态性质的加密函数是指两个明文a、b满足Dec(En(a)⊙En(b))=a⊕b的加密函数，其中En是加密运算，Dec是解密运算，⊙、⊕分别对应明文和密文域上的运算。当⊕代表加法时，称该加密为加同态加密：当⊙代表乘法时，称该加密为乘同态加密。

全同态加密是指同时满足加同态和乘同态性质，可以进行任意多次加和乘运算的加密函数。用数学公式来表达，即Dec(f(En(m1)，En(m2)，…，En(mk)))=f(m1，m2，…，mk)，或写成：f(En(m1)，En(m2)，…，En(mk))=En(f(m1，m2，…，mk))，如果f是任意函数，称为全同态加密。

直到2009年，IBM的研究人员Gentry首次设计出一个真正的全同态加密体制，即可以在不解密的条件下对加密数据进行任何可以在明文上进行的运算，使得对加密信息仍能进行深入和无限的分析，而不会影响其保密性。经过这一突破，存储他人机密电子数据的服务提供商就能受用户委托来充分分析数据，不用频繁地与用户交互，也不必看到任何隐私数据。同态加密技术允许公司将敏感的信息储存在远程服务器里，既避免从当地的主机端发生泄密，又依然保证了信息的使用和搜索；用户也得以使用搜索引擎进行查询并获取结果，而不用担心搜索引擎会留下自己的查询记录。为提高全同态加密的效率，密码学界对其研究与探索仍在不断推进，这将使得全同态加密越来越向实用化靠近。1

相关概念同态加密的思想起源于私密同态，代数同态和算术同态是私密同态的子集。

R 和 S 是域，称加密函数 E：R→S 为：

加法同态，如果存在有效算法⊕，E(x+y)=E(x)⊕E(y)或者 x+y=D(E(x)⊕E(y))成立，并且不泄漏 x 和 y。

乘法同态，如果存在有效算法 ，E(x×y)=E(x) E(y)或者 xy=D(E(x) E(y))成立，并且不泄漏 x 和 y。

混合乘法同态，如果存在有效算法 ，E(x×y)=E(x) y 或者 xy=D(E(x) y)成立，并且不泄漏 x。

减法同态，如果存在有效算法○- ，E(x-y)=E(x)○- E(y)或者 x-y=D(E(x)○- E(y))成立，并且不泄漏 x 和 y，则称 E 为减法同态。

除法同态，如果存在有效算法○/ ，E(x/y)=E(x)○/ E(y)或者 x/y=D(E(x)○/ E(y))成立，并且不泄漏 x 和 y，则称 E 为减法同态。

代数同态，如果 E 既是加法同态又是乘法同态。

算术同态，如果 E 同时为加法同态、减法同态、乘法同态和除法同态。

主要应用云计算、电子商务、物联网、移动代码等。2

本词条内容贡献者为:

李嘉骞 - 博士 - 同济大学