目前,隐私计算“门派”众多,涉及的技术名词纷繁复杂,如何厘清其中的关联关系?本期九洲继续邀请到密码学专家、清华大学高等研究院助理研究员郑中翔博士梳理现代密码学研究领域,以及通用/专用多方安全计算技术路线。
密码学的研究可以划分成以下四个层次:
首先第一层是计算问题,它是密码学的基础困难性假设,例如NP不等于P。第二层是密码学原语,是实现了一些基础功能的算法,包括对称加密、公钥加密、杂凑函数、伪随机数生成器等。第三层是密码协议,他们基于密码原语来实现多种功能,比如隐私计算中非常火热的多方安全计算的概念,零知识证明的概念,以及可搜索加密等。第四层是通常基于密码协议来构建安全系统,属于多学科交叉的一个领域。这四层是一个层层递进的关系,每一层依赖于上一层的相应实现。
在密码学密码原语的研究中,通常除了基础的功能之外,还会考虑一些扩展功能的密码原语,例如基于身份的加密算法,基于属性的加密算法,同态加密算法、群签名、环签名、门限签名等等。那么以隐私计算为例,九洲来看看这些密码学原语的发展对密码协议有哪些影响。
可以看到上个世纪80年代,多方安全计算概念首次被提出,多方安全计算主要研究在没有可信第三方的情况下,如何安全地计算一个约定的目标函数的问题。在这样一个计算过程中,要求各方的数据都不会被其他方所知。它主要基于依赖的技术是秘密共享、不经意传输以及混淆电路,而这些密码协议依赖的密码原语是一些基础的加密算法,比如AES、RSA等等。
到了2000年左右,在半同态加密算法Paillier的基础上,一些专用的、特定场景的多方安全计算的功能得以更高效地实现,比如匿名投票等。而到了近年来,全同态加密逐渐走入应用,如何基于全同态加密构建高效的多方安全计算方案,则成了现在一个广泛讨论的问题。
全同态的概念最早从上个世纪80年代由Rivest等人提出,自2009年Gentry提出第一个全同态加密方案以来,已经发展为了三代,其中第一代以Gentry为代表,第二代典型的算法是BGV、BFV、CKKS等。第三代则是以GSW算法为基础的一些延伸算法。
这三代算法各有特点,第一代算法主要基于的困难性假设,是理想格陪集问题稀疏子集和问题,它的特点是理论上可行,但实际上的效率比较低。第二代的全同态加密则基于LWE/NTRU问题,它的优化比较充分,是目前效率最高的一类算法,在计算多项式运算的时候有较大优势。第三代算法则主要基于LWE问题,它的形式简洁,参数选取更简便,主要优势集中在逻辑运算上。
从安全多方计算的目标函数来看,安全多方计算可以分为通用安全多方计算及专用多方安全计算,通用安全多方计算顾名思义就是支持任意目标函数的计算,协议可以应用于不同的场景,易于设计。专用多方计算则支持某些特定的函数,因此需要针对特定的问题来设定具体的解决方案。它的特点是在解决部分问题时效率很高,但难以应用到其他场景上,例如隐私集合求交问题、门限密码等。
刚才九洲谈到了多方安全计算、混淆电路等等各种不同的密码学概念,那么他们在隐私计算/联邦学习中到底发挥什么样的作用,这些概念之间的联系又是什么样,下面九洲来看一下他们之间的结构关系。
为了实现隐私计算/联邦学习这一目标,可以使用通用安全多方计算或者专用多方安全计算的方式,通用安全多方计算,主要技术包含混淆电路、不经意传输以及秘密共享,而专用多方安全计算则种类多样,例如通过基于秘密共享的专用安全多方计算,基于不经意传输的专用安全多方计算,以及基于半同态算法的专用多方安全计算,另外还有一类安全多方计算可以基于全同态加密算法来实现,对比于上述技术,全同态加密提出的时间较晚。
目前针对不同的场景,全同态加密算法可以分为Full HE和 Leveled HE两个分支,这两个分支可以分别用于设计通用及专用的安全多方计算方案。
下面九洲来看一下这些技术路线各自的优点和缺点,通用安全多方计算的两个路线都可以实现任意函数的隐私计算目标,这是他们共同的优点,而他们的主要问题也都是效率方面的:基于混淆电路的方案需要的计算及通讯开销较大,而基于Full HE 的方案则需要进行频繁的自举运算,这降低了算法的运行效率。
专用多方安全计算的四条路线在效率上都比较高,根据其能够实现计算功能的种类由多到少排列,第一是基于全同态加密算法的方案,基于全同态加密算法的方案可以实现任意已知函数的计算,但前提是需要针对这些函数设置合适的参数;基于秘密共享的方案则能够实现比较多的运算功能,但运算依赖第三方辅助,而且对于部分运算,计算及通讯开销也比较大。基于半同态算法的方案则功能比较有限,主要由加法或乘法两者之一构成。基于不经意传输的方案则功能更加单一,比如比较两个数据是否相同等。
当前市场上常见的隐私计算方案,主要由基于秘密共享,基于不经意传输以及基于半同态算法这三类专用多方安全计算路线组成,由于后两者能够实现的功能有限,许多计算需要通过秘密共享的方式完成,而依赖第三方这一缺点就成了方案实际应用过程中的最大挑战。
基于全同态算法设计的方案既能够满足上述计算的需要,又不依赖于第三方,这是基于全同态算法方案设计,对比于之前方案的一大优势。但由于全同态算法相关技术提出时间晚,发展速度快,且需要一定的专业知识,目前市场上仍未大范围推广。