作者：Steven Yue，原刊于作者知乎
前一阵子在斯坦福学习了CS355（高阶暗码学）的课程。给咱们上课的是Dan的三个PhD学生Dima Kogan，Florian Tramer和Saba Eskandarian。三个PhD讲师各有特色，研讨的方向也十分不同。Dima主攻隐私维护技能PIR（Private Information Retrieval），Florian主攻ML和区块链方面的研讨，而Saba主攻零常识证明。
CS355这一门课简直涵盖了从古至今暗码学范畴的一切内容。从最早的单向函数（One-way Function），到椭圆方程（ECC）和Pairing，最终到一些近几年比较热的MPC、零常识、私有信息检索（PIR）、全同态算法等等。因为前两天刚刚结课，趁着常识内容还在浅层回忆中没有遗忘，整理了一波笔记。课程内容十分有趣，其余的内容以后有时间跟咱们渐渐共享～
这一期，咱们来讲一讲最近很火的全同态加密（FHE）与伴随而来的格加密（Lattice-based Encryption）技能。
全同态加密是什么
信任许多朋友现已多少听说过全同态加密（Fully Homomorphic Encryption/FHE）的台甫了。近几年关于个人隐私维护的论题越来越多，包括同态加密在内的一系列暗码学应用技能也得到了很广泛的遍及。
为了更好的了解这个论题，我想要再对全同态加密这个界说稍作介绍一下。
加密系统回忆
在开端之前，咱们先温习一下最最传统的加密系统。
咱们都知道，假定要构建一个加密系统，往往都需求一个密钥（Key）。经过这个密钥，咱们能够一头把明文的信息加密成密文，然后在另一头经过密钥再把密文变回本来的姿态。假定没有这个Key的话，其他的人很难知道咱们到底传递了什么信息。
上文的图例基本展示了一切常见加密系统的全貌。一切的加密系统，假定用比较正式的描绘办法，无疑是做了三件事：
对加密算法有所了解的朋友，必定会知道常见的一些加密算法，比方说AES，RSA等等。咱们必定也会知道一般来说加密系统分为两种：对称加密系统和非对称加密系统。咱们这儿描绘的这三个步骤，其实通用于任何加密系统。假定是对称的，那么加密和解密用的密钥便是一样的。假定是非对称的系统的话，那么加密用的便是公钥（Public Key），然后解密用的是不一样的私钥（Private Key）。
在暗码学研讨中，每当咱们看到一个新的系统的界说之后，接下来往往都要陈述这个系统所应具有的特点（Properties）。
语义安全的首要意义在于旁观者无法区别两条加密的音讯。那么假定有入侵者窃听网络，看到了我宣布的加密信息，只要我使用的加密系统是语义安全的，那么我就能够坚信入侵者无法从密文中得到关于加密内容的任何信息。
满意了上述两条特点之后，一个加密系统就变得健全啦。
同态加密：偶然的特殊性质
了解完加密系统是怎么一回事之后，咱们能够来关注一下这个看似像随机生成的乱码一样的密文。咱们都知道，光看密文自身，咱们什么信息都不会得到。可是这是不是就代表，假定没有密钥只要密文，咱们什么都不能做了呢？
答案咱们都知道：其实并不是。
关于这种特点，咱们称之为加法同态。意思便是说，加密往后的密文与以前的原文保持着一种微妙的代数联系。假定咱们把密文累加起来，咱们就能够获得把原文相加起来加密往后的新密文。同理可得，加法同态至于，还存在着乘法同态的加密算法。一个乘法同态的算法生成的密文，咱们能够相乘起来，然后获得原文之间相乘之后的成果所对应的密文。整个过程中，咱们不需求知道任何和密钥有关的信息，纯粹仅仅把看似像随机乱码的密文组合起来。
举个比方：匿名投票系统
下面，咱们来举一个比方，生动的描绘一下同态加密的实用性。
咱们都知道在线投票是怎样的——假定一个公司的老板想要发起一波投票，选择公司是否要采纳996的制度。那么老板能够让IT设置一个服务器，让职工提交自己的选择：投0代表不想，投1代表想。最终投票阶段完毕之后，老板就能够把一切的投票加在一同。假定最终一切票的总和超越了职工人数的一半，那么公司就会开端996。
这个投票机制看起来很简略，可是有一个很大的隐私问题：假定老板心中就想让全员996，然而仅仅成心发起了这个投票来垂钓执法，看看哪个职工不愿意加班，那么老板能够悄然委托自己的小弟在网络上偷听，把每一个职工提交的选择都记录下来，最终看到底是谁投了0。这样一来，职工都十分害怕，不敢吐露自己的心声。
假定咱们能够使用加法同态的加密算法的话，那么这个问题就很好处理了。
当然，这个系统还十分的不完整，比方IT部分能够直接协助老板把每个人的投票解密开来，然后记录成一个文档。关于这个问题还有别的暗码学东西能够帮咱们来处理。因为篇幅原因就在这儿不多阐明啦。
不过到这儿，咱们应该能够感受到同态加密算法的强壮了。咱们能够这样了解：经过同态加密算法，用户能够与一个不可信的远程服务器（云端）进行某种安全署理核算（Secure Delegated Computation）。用户能够经过同态加密的技能来把自己灵敏的隐私输入加密后托付给云端，然后云端能够在加密往后的数据上进行必定程度的核算，最终得到加密往后的用户想要的成果，而且返还给用户。最终用户就能够用解密密钥来翻开得到的成果了。整个协议中，被署理方（云端）始终都无法看到任何和私密输入有关的有用信息。
同态加密系统的分类
大致了解了两种最基础的同态性质之后，其他的概念就变得十分容易了解了。假定系统性的来看，同态加密系统大致上被分为四类：部分同态、近似同态、有限级数全同态与彻底同态。
下面，咱们就来依次看一下每一个类别的详细界说。
部分同态加密（Partially Homomorphic Encryption)
同态加密最初级的阶段被称为部分同态加密，界说便是密文只要一种同态特性。这一阶段就包括了咱们上文所描绘的加法同态与乘法同态两种模式。
咱们就得到了这两条音讯相乘之后所对应的密文！这便是乘法同态性质了，咱们能够接着这条密文继续往上叠加新的密文，这样一来咱们就能够得到密文之间恣意的相乘。
近似同态加密（Somewhat Homomorphic Encryption）
就如同咱们在上一段所说，假定咱们又想让私密输入相乘，又想得到它们之间的线性组合的话，单纯的部分同态加密算法（RSA，ElGamal）是无法完结的。所以咱们就需求来到下一阶段。
部分同态加密的下一阶段是近似同态加密，这一阶段间隔咱们想要完成的全同态更近了一步。假定咱们有近似同态加密算法的话，那么咱们就能够在密文上同时核算加法与乘法了。可是需求注意的是，正因为这一阶段是近似同态（Somewhat Homomorphic）的，所以能够做的加法和乘法次数十分有限，能够核算的函数 F
近似同态加密这一阶段常见的比方并不多，假定说最好了解的比方的话，那就应该是根据配对（Pairing）的循环群加密算法了。
上文咱们简略的评论过根据普通循环群的ElGamal加密算法。咱们都知道这一算法是加法同态的，也便是说能够得到恣意密文之间的线性组合。事实上，在某些特殊的循环群中，咱们还能够找到一些薄弱的乘法同态性质。
这一局限性证明了这个系统是近似同态的，因为咱们不能核算恣意逻辑和深度的函数F。
有限级数全同态加密（Fully Leveled Homomorphic Encryption）
来到下一个阶段之后，咱们间隔全同态的方针更进一步了。
这一阶段被称之为有限级数全同态加密。在这一阶段的话，咱们现已能够对密文进行恣意的加法乘法组合了，没有任何关于次数的局限性。
全同态加密（Fully Homomorphic Encryption，FHE）
千呼万唤使出来，最终就到咱们拭目以待的全同态加密（FHE）了。
就像姓名所说的一样，一个全同态加密的系统没有任何核算办法的约束，咱们能够在没有密钥的情况下，把密文恣意的组合起来，构成新的密文，而且新的密文，不管核算的复杂度，都能够完美的被还原成原文。
当咱们到达这一阶段的时分，之前说到的安全署理核算就变得可行了。假定能够找到一个功率比较高的全同态加密系统的话，咱们能够安全的把一切本地的核算全部署理到云端，而且不会泄露任何一丁点数据！
全同态加密系统的界说
在开端下文关于全同态前史的评论之前，咱们能够系统性的界说一下全同态系统的正式界说。一个全同态加密系统，一共具有四个算法：
全同态加密的前史回忆
在开端学习全同态加密算法到底是怎么完成的之前，咱们无妨来看看全同态加密这个概念到底是怎么来的。
FHE（全同态）的概念其实在上世纪70年代末就现已被提出了。1978年，暗码学界的几个大牛Rivest，Adleman和Dertouzos在他们的论文On Data Banks and Privacy Homomorphisms中第一次说到了关于密文进行必定的核算，能够间接地对原文进行操作的系统构想。到后来这一主意就被从头总结命名为全同态加密了。
由此可见，全同态加密这一概念现已被提出了好久了。令人惊讶的是，1976年，也便是论文宣布的两年前，Diffle-Hellman密钥交换协议才刚刚被提出！由此可见暗码届大牛的想象力仍是十分丰富的。
当FHE的概念被提出来之后，整个学术界都为之所动，开端了长达几十年的查找，企图找到一个具有全同态性质的完美算法。可是这几十年下来，人们试遍了一切能够想到的选择，可是找不到一个又能满意全同态一切条件，而且安全性能够被轻易证实的选项。
直到2009年，在斯坦福读书的PhD Craig Gentry忽然灵光一现，攻破了FHE算法的难关。在他的博士毕业论文中，他第一次给出了一个合理而且安全的全同态加密系统！这一系统根据理想格（ideal lattice）的假定。Gentry09提出来的全同态系统，咱们往往称之为第一代全同态加密系统。
在Gentry的论文中，他还说到了一个至关重要的概念叫做Bootstrapping。Bootstrapping是一种关于密文的特殊处理技巧，处理往后竟然能够把一个噪音接近临界值的密文“从头改写”成一个噪音很低的新密文。经过Bootstrapping，一个有限级数的系统的噪音能够永久不超越临界值，然后变成了全同态的系统。这样一来，咱们就能够同态核算恣意大小的F
在Gentry的重大突破之后，整个暗码圈又一次陷入了张狂，咱们都开端争相根据Gentry提出的主意寻找愈加高功率和万能的全同态系统。
在2011年的时分，两位大佬Brakerski和Vaikuntanathan提出了一个新的全同态加密系统，这一系统根据格（lattice）加密的另一种假定Learning With Errors（LWE）。在同一年，Brakerski，Gentry与Vaikuntanathan这三人一同把这个系统做完了，而且正式宣布出来。他们发明的全同态系统简称为BGV系统。BGV系统是一个有限级数的同态加密系统，可是能够经过Bootstrapping的办法来变满足同态系统。BGV系统相比起Gentry09提出的系统，使用了愈加实际一点的LWE假定。一般来说咱们都把BGV系统称之为第二代全同态加密系统。
2013年，Gentry又东山再起了。Gentry，Sahai和Waters三个大佬推出了新的GSW全同态加密系统。GSW系统和BGV相似，自身具有有限级数全同态性质，根据愈加简略的LWE假定，而且经过Bootstrapping能够到达全同态。咱们一般把GSW系统称为第三代全同态加密系统。
2013年之后，暗码圈基本上就百家争鸣了。根据本来的三代全同态系统之上，呈现了各种各样新的规划，致力于优化和加快BGV与GSW系统的运行功率。IBM根据BGV系统开发了一个开源的全同态运算库HElib，而且成功的移植到各大移动平台上。与此同时，还有另外一个开源项目TFHE也十分值得注意。TFHE是根据GSW系统，又加以了各种优化与加快，现在也十分的有名。
在开发传统的全同态库之外，也有许多团队在研讨怎么经过GPU，FPGA，ASIC等异构硬件来更好的加快全同态加密算法的核算。比方cuFHE便是一个比较有名的根据CUDA的GPU加快全同态加密系统。
站在今日的角度上，一路看来，全同态系统的大门被Gentry大神敲开现已过去了11年了。现在业界关于FHE的研讨百家争鸣，不少人都在不同的角度和应用需求上在研讨全同态系统。直到今日，咱们现已具有了多种可行的FHE完成办法，可是现在咱们还在不断寻求的是FHE系统运转的功率。拿现在最前沿的FHE库来说，在移动平台上同态核算一些比较简略的逻辑可能要少则花上几十毫秒，多则花费几十秒的时间。这些时间单位关于核算机系统来说是极其缓慢的。
怎么能够让FHE系统愈加高功率的在异构平台上运行，仍然是一个未解之谜。假定这道难题一旦被处理了，那么把一切的电脑运算都转为全同态，署理在第三方的云端上进行核算，都是伸手可得的未来。
FHE与MPC的联系
在完毕文章之前，我还想弥补阐明一下FHE与MPC之间的联系。MPC即Secure Multi-Party Computation，便是可信多方核算。一般代表的是有多方具有自己的私密输入，不想泄露给别人，可是他们想使用自己的输入一同核算一个函数 F
MPC其完成已是一个十分广为人知，而且被研讨了好久的一个范畴了。自从上个世纪暗码学家姚期智推出了他的Garbled Circuits之后，MPC范畴获得了十分广的认可，而且也有许多突破。现在咱们现已具有许多能够使用的MPC库，而且也具有必定的运行功率了。
假定了解MPC的朋友，看到全同态加密系统的艰苦前史之后，或许会有许多疑问：为什么不能够直接经过一个MPC协议来代替全同态加密呢？
的确，一个MPC协议能够彻底代替一个FHE协议。咱们只需求把用户和私密输入作为一个协议中的一个Party，再把远程的署理核算服务器作为另一个Party，就满意了MPC协议履行的条件，只需求经过必定的交互，就能够完成署理核算，而且服务器也看不到私密输入。
可是有很重要的一点咱们疏忽了：因为MPC是有交互性的，所以需求用户和服务器共同进行核算与沟通才能够完结协议。这也就和FHE署理核算最根本的需求冲突了。假定用户需求一直保持在线完结协议，而且也要支付一部分算力的话，那其实核算根本就没有被“署理”出去，双方仅仅为了信息的安全性而在做更多的核算。这也阐明了为什么MPC范畴现已得到重大突破了，可是FHE的范畴仍然是一片不知道，因为他们两个系统处理的是彻底不同的问题。
下一站：GSW全同态加密系统
看到这儿，想必咱们现已关于全同态加密系统有了十分透彻的了解。
下一站，咱们能够一同来学习一下前文说到的GSW全同态加密系统。虽然说这是全同态系统的第三代，可是我认为Gentry09，BGV，GSW这三套系统中用到假定最少，构造最简略，而且最容易了解的便是GSW了。而且现在也有许多开源库（如TFHE）便是根据GSW系统构建的。
因为篇幅原因，咱们就在这儿完毕这一篇文章吧。下一篇文章，咱们能够首要学习一下GSW系统的基础：根据格（lattice）的加密系统与LWE问题。一旦了解了LWE问题之后，GSW处理的问题就变得十分明晰了。
此时快讯
【FTX攻击者再次将1.5万枚ETH转至THORChain】金色财经报道，据Scopescan监测数据显示，FTX攻击者再次将15000枚ETH（2450万美元）转至THORChain。到目前为止，他已转出9万枚ETH（1.47亿美元）。大多数ETH都兑换成BTC并桥接至比特币链。该巨鲸仍然在以太坊上拥有95748枚ETH（1.57亿美元）。
