很巧,正是我的研究方向,我专栏中也写了很多同态加密和安全多方计算的文章,可以去我专栏学习,欢迎交流。下面我就抛出一些自己的理解。
近两年,同态加密和安全多方计算确实是火了,以前只是在学术界,现在慢慢的渗透到了工业界。除了学术界大牛们的努力,这和计算机和通信技术的快速发展也是离不开的。
下面简单说一下同态加密和安全多方计算是什么。
同态加密
在讲同态加密前,我们先来说下传统的加密(这里传统的加密,可以是对称加密,如AES、SM4,也可以是公钥加密,如RSA、ECC、SM2)。
加密和解密通常是成对存在的,如下图,数据在被Party A加密消息"Hello!"后,将会生成一个和(伪)随机数不可区分的的密文。将密文发送至Party B后,Party只有在解密后才能获得明文信息"Hello!"。
这个流程走下来是没什么问题的。只要加密算法是语义安全的,且密钥得到妥善管理,那么我们就可以相信密文是安全的。
那么我们现在想象一个情景,如果密文被存储在了一个不可信的第三方中,现在 Party A 需要对密文进行更新,那我们该如何做呢?
大家肯定会想到,Party A将密文下载下来,解密后,再进行更新,更新完后的数据重新上传到第三方。
这个过程也没有什么问题,很简单明了。但是,细心朋友会发现,整个过程需要添加两次通信(下载和上传)和两次计算开销(解密和加密计算)。
那么,我们想,是不是可以直接在计算能力更强的第三方上直接对密文更新呢?如此,便可以为Party A 节省两次通信和两次计算开销。
完美。那传统的加密算法能完成这项重大任务吗?
经过研究发现,有些算法在固定的应用场景中是可以满足的。比如,RSA可以在密文状态下进行同态乘法计算,Paillier可以在密文状态下进行同态加法计算。这些类似的算法,我们称其为部分同态加密,即只能执行部分类型的同态加密。
有了部分同态加密,我们想,是不是有可以计算任意函数的同态加密算法呢?前辈们说,有!此时,Gentry在09年,带着第一个全同态加密来了。在此之后,全同态加密得到了快速发展。GSW、FHEW、TFHE、BFV、BGV、CKKS等重量级方案被提出。
全同态加密发展到今天,已经出现了两个分支,一个分支是以计算算数电路为主(BFV, BGV, CKKS),另一个则以计算布尔电路为主(FHEW, TFHE)。
其中 FHEW、TFHE、GSW为布尔电路上的实现,其特性
- 快速比较
- 支持任意布尔电路
- 快速 bootstrapping(噪声刷新过程,减少因密文计算而产生的噪音,降低失败可能性)
BGV、BFV是算数电路上的实现,其特性
- 在整数向量上进行高效的SIMD计算(使用批处理)
- 快速高精度整数算术
- 快速向量的标量乘法
- Leveled design(通常不使用bootstrapping)
CKKS则是17年才提出来的,其特性
- 快速多项式近似计算
- 相对快速的倒数和离散傅里叶变换
- 深度近似计算,如逻辑回归学习
- 在实数向量上进行高效的SIMD计算(使用批处理)
- Leveled design(通常不使用bootstrapping)
每个分支都得到了快速的发展。但是,在很多时候,我们要计算的是比较综合的函数,既有布尔计算,又有算数计算,那此时我们选什么方案好呢?我们选以上哪个方案都会有缺陷,那我们是不是可以设计一个兼容两个分支的方案?
CHIMERA踏着七彩祥云来了。PEGASUS是2020年最新研究成果,效率优于CHIMERA。
至此,同态加密的大体发展路线已经给出了,显而易见,学习路线也给出了。下面重复一下:
现在网上学习下同态加密的基础知识,可以来我专栏:
有了基础知识,就可以按照以下论文列表进行深入学习了。
- GSW: Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based .
- FHEW: Bootstrapping Homomorphic Encryption in Less Than a Second.
- TFHE: Fast Fully Homomorphic Encryption Over the Torus.
- BFV: Somewhat Practical Fully Homomorphic Encryption.
- BGV: (Leveled) Fully Homomorphic Encryption without Bootstrapping .
- CKKS: Homomorphic Encryption for Arithmetic of Approximate Numbers.
- CHIMERA: Combining Ring-LWE-based Fully Homomorphic Encryption Schemes.
- PEGASUS: Bridging Polynomial and Non-polynomial Evaluations in Homomorphic Encryption.
等把上面的文章都读完之后,同态加密也就掌握的差不多了。
以上便是同态加密学习路线。下面我们来看下安全多方计算的基础知识和学习路线。
安全多方计算
很多小伙伴尝试深入学习安全多方计算,但在读过一两篇文章之后就被劝退了。由于安全多方计算包含众多密码学原语,学习门槛较高,特给出学习路线,帮大家缕清学习思路。本篇文章不讲具体技术,只推荐学习方法。
很多小伙伴催SMPC的学习路线了,本来答应在周末找个时间写一下,担心周末再有事情,所以就提前了。
0.1 首先给出初学所使用的读本和综述文章;
0.2 然后给出深入学习需要精读的文章;
0.3 最后给出文章中提及的阅读材料下载链接,我会给大家打包好,给出统一下载链接。
当然,在文章叙述时,也会给出对应文章的链接,大家可根据自己的习惯来下载阅读。
初学
想要进入一个学科,那该学科的圣经读本是必不可少的,下面给出几部大而全的SMPC圣经读本:
- 《A Pragmatic Introduction to Secure Multi-Party Computation》- 本书是对安全多方计算领域的广泛介绍,涵盖了基本结构和许多最新的改进。本书强调的是协议背后的直觉和想法,而不是严格的证明。.
- 《Applications of Secure Multiparty Computation》- 收集了一些现实世界任务(如统计)的MPC协议。
- 《Efficient Secure Two-Party Protocols》- 全面研究安全两方计算的高效协议和技术,既包括可用于安全计算任何功能的一般结构,也包括感兴趣的具体问题的协议。
- 《Secure Multiparty Computation and Secret Sharing》- 全面处理多方计算(MPC)和秘密共享的无条件安全技术。
前两本数是必读的。第一本是2018年,也是最新的相关书籍,对于初学者阅读难度较高。第二本是2015年的,阅读难度适中。因此,建议大家先读第二本,再读第一本。
对应下载链接:
- https:// securecomputation.org/
- IOS Press Ebooks
除了以上书籍的阅读,建议大家还要读一些最新的综述文章:
- Secure Multiparty Computation (MPC)2020-Yehuda Lindell
对应下载链接:
- https:// eprint.iacr.org/2020/30 0.pdf
通过以上阅读,大家应该能够对SMPC有一个初步的掌握,至少可以知道SMPC的定义、安全性假设、有哪些构造方法、对应使用的密码学原语有哪些等。掌握以上知识后,我们便可以进行深入学习了。
深入学习
通过以上书籍阅读,我们对SMPC的构造分类应该有所了解,大体分为以下流派:
- Yao's GC,即姚期智院士开创的基于混淆电路系列
- SPDZ,即Ivan Damgard开创的基于秘密共享和有限同态加密系列
- ABY,包含了ABY和ABY3
对于GC系列建议阅读以下文章(文章名称后直接跟下载链接了,第一个是姚院士的开创之作,后面几篇是近些年的优化方案):
- Protocols for Secure Computations (Extended Abstract): https://crysp.uwaterloo.ca/courses/pet/F11/cache/www.cs.wisc.edu/areas/sec/yao1982-ocr.pdf
- Improved Garbled Circuit: Free XOR Gates and Applications:http://www.cs.toronto.edu/~vlad/papers/XOR_ICALP08.pdf
- FairplayMP – A System for Secure Multi-Party Computation:https://www.cs.huji.ac.il/~noam/FairplayMP.pdf
- Two Halves Make a Whole Reducing Data Transfer in Garbled Circuits using Half Gates:https://eprint.iacr.org/2014/756.pdf
- Fast and Secure Three-party Computation: The Garbled Circuit Approach:https://static.googleusercontent.com/media/research.google.com/zh-CN//pubs/archive/43888.pdf
对于SPDZ系列建议阅读以下文章(本系列有太多的文章,暂时只推荐以下三篇吧,第一篇和第三篇重点阅读,尤其第三篇):
- Multiparty Computation from Somewhat Homomorphic Encryption:https://eprint.iacr.org/2011/535.pdf
- Practical Covertly Secure MPC for Dishonest Majority Or: Breaking the SPDZ Limits:https://eprint.iacr.org/2012/642.pdf
- SPDZ2k: Efficient MPC mod 2k for Dishonest Majority:https://eprint.iacr.org/2018/482.pdf
对于ABY系列,当然就是以下两篇文章了:
- ABY – A Framework for Effificient Mixed-Protocol Secure Two-Party Computation:https://encrypto.de/papers/DSZ15.pdf
- ABY3 : A Mixed Protocol Framework for Machine Learning:https://eprint.iacr.org/2018/403.pdf
其实读完以上文章,大家应该就要往SMPC的应用方面过度了,现今,SMPC的最火热应用当属隐私保护机器学习(PPML)了。对于PPML的学习路线我就不推荐了,大家可以直接去我“隐私计算”专栏中阅读学习。
写在最后
啰嗦一句,SMPC涵盖的密码学原语非常广泛,大家在阅读我推荐的以上资料时,一定记得同时学习相应的密码学原语,比如OT,同态承诺,同态加密,秘密共享,零知识证明等等。
下面给出大家一个总的下载链接,里面包含了一些上面没有提到的文章,有兴趣的话可以当做扩展读本:
SMPC 链接:https://pan.baidu.com/s/1TRNmX_2xumuBepTLo3jgRw
提取码:c81t