百科问答小站 logo
百科问答小站 font logo



有哪些学习同态加密和安全多方计算等隐私计算的资料或学习路线? 第1页

  

user avatar   an-quan-xiao-qi 网友的相关建议: 
      

很巧,正是我的研究方向,我专栏中也写了很多同态加密和安全多方计算的文章,可以去我专栏学习,欢迎交流。下面我就抛出一些自己的理解。

近两年,同态加密和安全多方计算确实是火了,以前只是在学术界,现在慢慢的渗透到了工业界。除了学术界大牛们的努力,这和计算机和通信技术的快速发展也是离不开的。

下面简单说一下同态加密和安全多方计算是什么。

同态加密

在讲同态加密前,我们先来说下传统的加密(这里传统的加密,可以是对称加密,如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圣经读本:

  1. 《A Pragmatic Introduction to Secure Multi-Party Computation》- 本书是对安全多方计算领域的广泛介绍,涵盖了基本结构和许多最新的改进。本书强调的是协议背后的直觉和想法,而不是严格的证明。.
  2. 《Applications of Secure Multiparty Computation》- 收集了一些现实世界任务(如统计)的MPC协议。
  3. 《Efficient Secure Two-Party Protocols》- 全面研究安全两方计算的高效协议和技术,既包括可用于安全计算任何功能的一般结构,也包括感兴趣的具体问题的协议。
  4. 《Secure Multiparty Computation and Secret Sharing》- 全面处理多方计算(MPC)和秘密共享的无条件安全技术。

前两本数是必读的。第一本是2018年,也是最新的相关书籍,对于初学者阅读难度较高。第二本是2015年的,阅读难度适中。因此,建议大家先读第二本,再读第一本。

对应下载链接:

  1. securecomputation.org/
  2. IOS Press Ebooks

除了以上书籍的阅读,建议大家还要读一些最新的综述文章:

  1. Secure Multiparty Computation (MPC)2020-Yehuda Lindell

对应下载链接:

  1. eprint.iacr.org/2020/30

通过以上阅读,大家应该能够对SMPC有一个初步的掌握,至少可以知道SMPC的定义、安全性假设、有哪些构造方法、对应使用的密码学原语有哪些等。掌握以上知识后,我们便可以进行深入学习了。

深入学习

通过以上书籍阅读,我们对SMPC的构造分类应该有所了解,大体分为以下流派:

  1. Yao's GC,即姚期智院士开创的基于混淆电路系列
  2. SPDZ,即Ivan Damgard开创的基于秘密共享和有限同态加密系列
  3. ABY,包含了ABY和ABY3

对于GC系列建议阅读以下文章(文章名称后直接跟下载链接了,第一个是姚院士的开创之作,后面几篇是近些年的优化方案):

  1. Protocols for Secure Computations (Extended Abstract): crysp.uwaterloo.ca/cour
  2. Improved Garbled Circuit: Free XOR Gates and Applications:cs.toronto.edu/~vlad/pa
  3. FairplayMP – A System for Secure Multi-Party Computation:cs.huji.ac.il/~noam/Fai
  4. Two Halves Make a Whole Reducing Data Transfer in Garbled Circuits using Half Gates:eprint.iacr.org/2014/75
  5. Fast and Secure Three-party Computation: The Garbled Circuit Approach:static.googleusercontent.com

对于SPDZ系列建议阅读以下文章(本系列有太多的文章,暂时只推荐以下三篇吧,第一篇和第三篇重点阅读,尤其第三篇):

  1. Multiparty Computation from Somewhat Homomorphic Encryption:eprint.iacr.org/2011/53
  2. Practical Covertly Secure MPC for Dishonest Majority Or: Breaking the SPDZ Limits:eprint.iacr.org/2012/64
  3. SPDZ2k: Efficient MPC mod 2k for Dishonest Majority:eprint.iacr.org/2018/48

对于ABY系列,当然就是以下两篇文章了:

  1. ABY – A Framework for Effificient Mixed-Protocol Secure Two-Party Computation:encrypto.de/papers/DSZ1
  2. ABY3 : A Mixed Protocol Framework for Machine Learning:eprint.iacr.org/2018/40

其实读完以上文章,大家应该就要往SMPC的应用方面过度了,现今,SMPC的最火热应用当属隐私保护机器学习(PPML)了。对于PPML的学习路线我就不推荐了,大家可以直接去我“隐私计算”专栏中阅读学习。

写在最后

啰嗦一句,SMPC涵盖的密码学原语非常广泛,大家在阅读我推荐的以上资料时,一定记得同时学习相应的密码学原语,比如OT,同态承诺,同态加密,秘密共享,零知识证明等等

下面给出大家一个总的下载链接,里面包含了一些上面没有提到的文章,有兴趣的话可以当做扩展读本:

SMPC 链接:pan.baidu.com/s/1TRNmX_

提取码:c81t




  

相关话题

  请教DH算法在混合加密中,到底起什么作用? 
  信息论的冗余剔除应用与密码学破解? 
  存在利用魔方性质的加密算法吗? 
  谁对于enigma加密机有比较好的解密算法? 
  有没有能向玩家保证服务器发牌时没有作弊的牌类游戏发牌算法? 
  随机确定密文的加密方式,密码有办法被破解吗? 
  Diffie-Hellman密码交换是如何运作的? 
  谁对于enigma加密机有比较好的解密算法? 
  西电为什么密码学排第一? 
  用无理数加密,如何破解? 

前一个讨论
浙江 25 岁已婚女子竟被查出染色体核型是男性,是什么原因导致的?她的生活该何去何从?
下一个讨论
第一次出国旅行的你,曾感受到了哪些文化上的冲击?





© 2024-11-09 - tinynew.org. All Rights Reserved.
© 2024-11-09 - tinynew.org. 保留所有权利