同态加密

定义

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

同态加密可以保证实现处理者无法访问到数据自身的信息。

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

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

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

同态性来自代数领域,一般包括四种类型:加法同态、乘法同态、减法同态和除法同态。同时满足加法同态和乘法同态,则意味着是代数同态,即全同态(Full Homomorphic)。同时满足四种同态性,则被称为算数同态。

对于计算机操作来讲,实现了全同态意味着对于所有处理都可以实现同态性。只能实现部分特定操作的同态性,被称为特定同态(Somewhat Homomorphic)。

问题与挑战

同态加密的问题最早在 1978 年由 Ron Rivest、Leonard Adleman 和 Michael L. Dertouzos 提出(同年 Ron Rivest、Adi Shamir 和 Leonard Adleman 还共同发明了 RSA 算法)。但第一个“全同态”的算法直到 2009 年才被克雷格·金特里(Craig Gentry)在论文《Fully Homomorphic Encryption Using Ideal Lattices》中提出并进行数学证明。

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

同态加密在云计算和大数据的时代意义十分重大。目前,虽然云计算带来了包括低成本、高性能和便捷性等优势,但从安全角度讲,用户还不敢将敏感信息直接放到第三方云上进行处理。如果有了比较实用的同态加密技术,则大家就可以放心的使用各种云服务了,同时各种数据分析过程也不会泄露用户隐私。加密后的数据在第三方服务处理后得到加密后的结果,这个结果只有用户自身可以进行解密,整个过程第三方平台无法获知任何有效的数据信息。

另一方面,对于区块链技术,同态加密也是很好的互补。使用同态加密技术,运行在区块链上的智能合约可以处理密文,而无法获知真实数据,极大的提高了隐私安全性。

目前全同态的加密方案主要包括如下三种类型:

  • 基于理想格(ideal lattice)的方案:Gentry 和 Halevi 在 2011 年提出的基于理想格的方案可以实现 72 bit 的安全强度,对应的公钥大小约为 2.3 GB,同时刷新密文的处理时间需要几十分钟。

  • 基于整数上近似 GCD 问题的方案:Dijk 等人在 2010 年提出的方案(及后续方案)采用了更简化的概念模型,可以降低公钥大小至几十 MB 量级。

  • 基于带扰动学习(Learning With Errors,LWE)问题的方案:Brakerski 和 Vaikuntanathan 等在 2011 年左右提出了相关方案;Lopez-Alt A 等在 2012 年设计出多密钥全同态加密方案,接近实时多方安全计算的需求。

目前,已知的同态加密技术往往需要较高的计算时间或存储成本,相比传统加密算法的性能和强度还有差距,但该领域关注度一直很高,笔者相信,在不远的将来会出现接近实用的方案。

函数加密

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

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

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