Page 162 - 计算机技术与网络安全研究

计算机技术与网络安全研究
Computer Technology and Cyber Security Research

2012 年研究人员利用一个内存足够大的机器在加密数据上计算 AES 函数，实验
结果表明，在一个数据块上计算 AES 函数的时间约为 40min，相比于在明文数据
块上的计算时间慢了六个数量级还多。
导致全同态加密方案低效的因素如下：密码方案本身的开销、计算模型所
带来的开销、高安全性所带来的开销。密码方案本身的开销主要集中在自举过程，

尽管已经有很多工作通过理论和工程实践来提高自举过程的效率，但是从最近的
实现来看，自举过程对于实际应用来说时间消耗依然过大。在计算模型方面，为
了使用全同态加密系统，需要事先将程序编码成布尔电路形式，而常见应用程序

编码后的布尔电路非常庞大、乘法深度很深。当乘法深度超过 3 或者加密非二进
制数据时，在一般商用机器上 HElib 的计算效率会变得非常慢（在秒这个数量级
上）。由于布尔电路乘法深度较深，需要将 recryption 操作加入计算过程，所以
会带来更高的计算开销。下面以数据库查询为例来说明。
假设服务器上存放一个学生信息表，其中一列为出生年份，其他列为姓名、

学校等信息，要执行的查询请求为“返回所有出生年份为 1990 年的学生姓名”。
如果在明文数据上执行该查询操作，可以通过建立快速搜索树，在对数阶时间复
杂度内完成搜索操作。但是如果该数据库使用了全同态加密方案进行加密，则必

须对整个数据库进行扫描，这是因为全同态加密满足语义安全，阻止服务器获取
有关明文数据的任何信息，甚至于某条数据是否满足查询条件这样的信息都不能
泄露。另外，有多少条记录满足查询请求这一信息也不能被服务器知道，为了防
止该信息泄露，假设查询请求和其对应的满足查询请求的结果集合为｛（Q1，
R1)，(Q2，R2)，…，(Qi，Ri)，…，(QN，RN)}，使用全同态加密时，对于任何

查询请求 Qi，为了达到语义安全，服务器返回的数据条数为 max{|Ri|}（其中 |·|
表示集合的基数）。一种极端的情况是：有一个不常见的查询条件，其返回的结
果是整个数据库，而满足其他查询请求的数据条目却很少，那么按照全同态加密

的安全要求，每次都要返回数据库中所有的数据条目，使查询本身失去了意义。
当数据库包含的数据量较大时，即使不是每次返回整个数据库，其通信开销依然
很大导致系统不可用。
综上所述，尽管理论上全同态加密是解决加密数据计算这一问题的最佳方
案，但是由于方案本身、计算模型以及高安全性带来的开销过高，使其无法在实

际中应用。不过一定程度上同态加密方案可用于解决一些乘法深度比较浅的加密

154
154