同态加密

定义

同态加密(Homomorphic Encryption)是一种特殊的加密方法,允许对密文进行处理得到仍然是加密的结果,即对密文直接进行处理,跟对明文进行处理再加密,得到的结果相同。从代数的角度讲,即同态性。

如果定义一个运算符 \triangle{},对加密算法 E 和 解密算法 D,满足:


E(X\triangle{}Y) = E(X)\triangle{} E(Y)

则意味着对于该运算满足同态性。

同态性在代数上包括:加法同态、乘法同态、减法同态和除法同态。同时满足加法同态和乘法同态,则意味着是 代数同态,即 全同态。同时满足四种同态性,则被称为 算数同态

历史

同态加密的问题最早是由 Ron Rivest、Leonard Adleman 和 Michael L. Dertouzos 在 1978 年提出,但 第一个“全同态”的算法 到 2009 年才被克雷格·金特里(Craig Gentry)证明。

仅满足加法同态的算法包括 Paillier 和 Benaloh 算法;仅满足乘法同态的算法包括 RSA 和 ElGamal 算法。

同态加密在云时代的意义十分重大。目前,从安全角度讲,用户还不敢将敏感信息直接放到第三方云上进行处理。如果有了比较实用的同态加密技术,则大家就可以放心的使用各种云服务了。

遗憾的是,目前已知的同态加密技术需要消耗大量的计算时间,还远达不到实用的水平。

函数加密

与同态加密相关的一个问题是函数加密。

同态加密保护的是数据本身,而函数加密顾名思义保护的是处理函数本身,即让第三方看不到处理过程的前提下,对数据进行处理。

该问题已被证明是不存在对多个通用函数的任意多 key 的方案,目前仅能做到对某个特定函数的一个 key 的方案。