全同态加密释疑（五）：为什么是电路观点

陈智罡

这个问题是许多刚接触全同态加密研究者困惑的一个问题。

也许初学者以为密码学都是基于数论观点的，其实真正的密码学的灵魂落脚点是计算复杂度。密码学中的所有方案必须要依赖于一个数学难题，这是其安全性所在的根本。问题有多难？拿什么来衡量？答曰：计算复杂度。所以有一本很有名但是很枯涩难懂的一本著名密码学理论书：《Foundations of Cryptography》（Oded Goldreich著），里面深刻阐述了这一观点。

但是电路观点在密码学中的方案由来已久。例如，姚期智的论文“How to generate and exchange secrets”就是通过布尔电路观点构造安全函数计算，产生了著名的概念“garbled circuit”。

强调一下，电路观点是一种计算复杂度的计算模型，用途是衡量解决问题所需要的资源，例如时间、存储量等。在电路计算模型下，有使用的gate的数量，电路的深度等。

为什么要使用电路观点来构造密码学中的方案？

采用电路计算模型的原因是电路模型需要“接触“到所有的输入数据，因而不会泄露任何信息，所以传统的安全计算都是采用电路模型的。尽管电路模型非常强大（等价于图灵机），但在某些方面图灵机计算模型要比电路模型的计算效率要高（例如折半查找）。例如在存储有n个数据项的数据库中，若使用标准的安全计算协议，首先把函数表示成电路进行计算，该协议的复杂度是Ω(n)。但是若使用图灵机计算模型下的二分查找，时间复杂度为О(logn)。

电路模型下，算法的性能是用最坏情况下的性能来衡量的。其原因是图灵机算法转换成电路模型下的算法后，该算法工作在无循环的算法结构下，这使得电路模型要考虑所有出现的情况，也就是最坏情况下的运行时间。简单的说，如果一个算法在实践中绝大多数的实例都是运行在多项式时间下，但是对于极少数实例时运行在指数时间下，那么电路模型的计算时间就是指数时间。

所以任何东西，此消彼长，都要付出代价的。

对于所有的全同态加密、基于属性加密、通用函数的两方及多方安全计算协议、对于通用函数的函数加密，都是采用的电路观点。

能否对于电路模型下的密码学方案，让其享受图灵机模型下的时间而不是最坏情况下的时间呢？

好消息：Shafi Goldwasser等人在今年的美密会上“Howto Run Turing Machines on Encrypted Data “论文中，提出了将一个图灵机算法编译成一个工作在电路上的算法（该算法可以看成被加密了），该算法运行在密文下，该电路上的算法的计算时间是图灵机模型下的算法计算时间。针对全同态加密方案、基于属性的加密方案、函数加密方案都进行了这种形式的尝试。

坏消息：这个被加密的运行在电路上的算法，泄露了图灵机模型下的算法计算时间。而且这些方案都是概念上的证明，并不是真正的一个实在的方案。所以意义并不大。