初探全同态加密：FHE的定义与历史回顾 前一阵子在斯坦福学习了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的话，其他的人很难知道我们到底传递了什么信息。 {% mermaid %} graph LR; pt[“Plaintext”] key[“EncKey”] –> enc[“Encryption”] pt –> enc; enc –> ct[“Ciphertext”] key2[“DecKey”] –> dec ct –> dec[“Decryption”] dec –> pt2[“Plaintext”] Keygen((Keygen)) -.- key Keygen -.- key2 {% endmermaid %} 上文的图例基本展示了所有常见加密体系的全貌。所有的加密体系，如果用比较正式的描述方法，无疑是做了三件事： 首先，通过一个生成算法$ KeyGen(1^{\lambda}) $来随机生成一对用于加密和解密的密钥$ (EncKey, DecKey) $。 加密方通过加密密钥$ EncKey $和加密算法$ Encryption $来加密原文$ Plaintext $，最后得到密文$ Ciphertext $。 随后，在解密的时候，解密方可以通过解密密钥$ DecKey $和解密算法$ Decryption $来解密密文，最后还原回来原来的原文。…

Preface Recently I have taken CS355 (Topics in Cryptography) at Stanford. This was a comprehensive course on advanced crypto topics. Throughout the 3-month course, the instructors covered various topics that span the history of Cryptography, starting from One-way Functions, PRFs all the way to applied cryptosystems such as MPC, Zero-Knowledge, and PIR. This was really a great course to take, and I’ve surely learned a lot about modern cryptosystems. In order to strengthen my understanding of these topics, I’ve decided to start a series of blog posts that (gently) introduces these cool crypto topics.…

This is a mirror of my post at https://medium.com/@stevenyue/mesmerizing-chameleon-signatures-4cdb3c8ab1c3. For the past year, I having been taking classes at Stanford under Professor Dan Boneh and learning about different topics in the field of Cryptography. It has truly become an amazing journey. There are so many marvelous ideas in this field and a lot of them essentially reshaped the world. Therefore I decided to start writing about what I have learned in a series of posts.…

浅谈零知识证明之三：zkSNARK证明体系的实现 距离上期更新已经过去了几个月了。前段时间回到美国之后，忙了好一阵子，这学期跟着Dan继续学习了密码学（CS255 Introduction to Cryptography）。这两天美国新冠疫情严重，封城在家里，正好有空把我的零知识证明笔记拿出来整理一下，继续写第三篇。 这一期，我们接着上一次讲过的数学运算电路，讲一讲简短零知识证明（zkSNARK）体系的具体实现和背后的原理。由于内容实在太多，我打算把这期的内容一分为二。 证明体系回顾 因为距离上一期已经过去了一段时间，我们可以先来回顾一下上次提到的简短证明体系的三个核心算法：Setup，Prove和Verify。 $Setup(C) \rightarrow (S_p, S_v)$：通过实现约定好的电路，生成后续需要使用的随机参数$S_p$和$S_v$。 $Prove(S_p, x, w) \rightarrow \pi$：通过公有输入$x$和私密输入$w$，生成零知识证明。 $Verify(S_v, x, \pi) \rightarrow Yes/No$：验证证明。 一个健全的零知识证明体系需要满足一定的要求。 第一条要求是完整性，也就是说如果秘密输入$w$满足了电路的要求，那么通过$w$生成的证明$\pi$一定可以被验证通过。用公式来表达就是： $$ Verify(S_v, x, Prove(S_p, x, w)) = Yes \iff C(x, w) = 0$$ 第二条要求是知识证明（Proof of Knowledge）， 换句话来说其实就是证明方一定得拥有一些我们没有的信息，我们需要知道这个$w$是真真切切存在的，是可以被提取出来的。具体的知识证明比较复杂，需要涉及到一个**提取器（Extractor）**的概念，详细可以参照郭宇老师的文章。 第三条要求就是简短证明（SNARK）。这个证明体系一定得简短高效才能满足我们的要求，不然抛开零知识的要求的话，还不如直接把原有的$w$直接告诉对方来的简单。用Big O来表示需要的时间和空间的话，具体是这样的： 证明所需时间：$time(P) = O( \mid C \mid )$， 和电路大小成正比。 证明大小：$ \mid \pi \mid = O(log \mid C \mid )$，和log电路大小成正比。 验证所需时间：$time(V) = O( \mid x \mid + log \mid c \mid )$，和公有输入$x$的大小再加上log电路大小成正比。 第四条要求就是零知识，也是相对来说最简单描述的要求。总的来说就是公有输入$x$和证明$\pi$不能暴露任何与私密输入$w$有关的信息。…

浅谈零知识证明之二：简短无交互证明（SNARK） 上一期文章发表之后，非常惊讶有那么多小伙伴读完了表示喜欢。那么我们接着这期继续吧！这次，我们专注的聊一聊SNARK。 相信看完前一篇文章的朋友们会有一点很不解的地方：为什么我们可以如此简短的创建一个证明，并且证明很长的信息呢？在上课前我也有这同样的疑惑，甚至觉得这个是一个“黑科技”，不过相信大家看完这篇文章，就会知道如何去驾驭这个“黑科技”了。 在详细讨论之前，我们得稍微严肃一点，系统性的学习一下SNARK的基本构造。 SNARK的四步构造 因为SNARK的“黑科技”特性，想要构建一套简短证明系统，其实流程是略微有些复杂的。总结一下一共可以分为四步，我们来一步一步详细描述。 第一步：确定有限域 $\mathbb{F}$ 在构造之前，我们先需要确定一个可以包含所有我们想要计算的数字的大小的一个有限域（Finite Field）$\mathbb{F}$。用通俗易懂的话来说，我们需要选一个很大很大的数字p，确保这个数字比我们要解决的问题里的所有数字都大。 如果以前了解过类似于RSA密码学的朋友们可能对这个概念不陌生。有限域就是给我们所有数字加了一个天花板，确定了整个数学系统的计算空间，类似于在电脑里如果我们想创建一个存数字的变量，我们需要思考到底是需要一个uint32_t（32位），还是一个uint64_t（64位）一样。所有超过有限域的值，都会直接溢出之后再倒回去从0开始。 在数学界，符合这个特性的计算空间其实有很多种，最常见的一种就是RSA算法里面用到的正整数求模一个大质数（integer mod p）。上文说到的找到一个数字p，其实就是一个很大的质数，然后我们可以用它来生成一个计算空间。 在确定计算空间之后，我们就可以真正开始SNARK的搭建了。 第二步：构建数学运算电路（Arithmetic Circuit） 当我们找到一个数字空间之后，我们下一步要做的事情，就是要把我们想要证明解决的问题用数学运算电路表示出来。 什么是数学运算电路呢？我们先来看一看传统的逻辑电路。 上图表述的是一个与非门（NAND）的电路。先不用过多了解电路的用处，我们可以发现的是，两组输入信号分别通过了NOT和AND这两个基础逻辑门。像AND和OR这样的基础逻辑门是逻辑电路的基础模块，通过拼加和堆叠我们可以实现任何复杂逻辑。 数学运算电路也是同理，只不过基础模块从逻辑门变成了数学运算。因为加法和乘法是最基础的数学运算，通过加法和乘法我们也可以近乎实现所有其他的运算方法，所以我们可以选用“加法门”和“乘法门”作为我们数学运算电路的基础模块。通过叠加运算门，我们可以搭建一个复杂多项式的“电路”。 为了能更好的理解运算门，我们来试试看把上面的NAND门从逻辑电路转换成数学运算电路。（假设Inp0和Inp1和原来逻辑电路一样，还是输入1/0的逻辑信号。 ） 我们先来看AND门：AND其实很简单，因为只有当Inp0和Inp1都是1的时候，AND的结果才会是1。我们很快发现，一个乘法门可以完美的代替AND门：只有当两个输入是1的时候，相乘得到的结果才会是1。 解决了AND之后，我们来转换NOT：NOT其实也非常简单，因为输入信号只会是0或者1，只要用1减去输入的信号，得到的结果就是相反的了。注意有一个问题是，因为我们只有加法和乘法，所以如果需要实现减法的话，我们需要先把输入信号乘上一个常数-1。 经过如此转换，我们就成功的把一个逻辑电路转换为数字逻辑电路了。同时因为我们已经知道如何组建AND和NOT了，理论上我们就可以把这两个部分模块化，拼接任意的复杂逻辑出来。 看到这里，你可能会觉得运算电路非常简单，和逻辑电路转化也非常直白。但是其实这是因为我们一直在假设运算电路的输入和逻辑电路一样，都是0或者1。在真实场景下，一个运算门的输入值可能上限非常大（取决于我们有限域选择的大小）。所以我们必须要想办法约束我们运算电路的输入，使其不仅能够在功能性上和逻辑电路相同，并且在输入取值上只可以取$[0,1]$这两个数字。 但是怎么用运算门来表示这么一个关系呢？因为数学运算电路其实就是一个复杂的多项式（比如上图的NAND电路就变成了Out = 1 - Inp0 * Inp1），我们可以把这个问题转化一下：**能否创造出一个多项式，只有当一个输入满足$[0,1]$的取值范围的时候，才会输入0？**最后我们发现，有这么一个多项式可以满足这个要求：$$ n \in [0, 1] \iff n \cdot (n-1) = 0$$ 上面这串表达式的意思是，只有当数字n取值于$[0,1]$这个范围的时候，后面的多项式$n \cdot (n-1)$才会输出0。也就是说，我们就可以把上文提到的Inp0和Inp1接到这个多项式转换成的运算电路内，只要这个运算电路的输出结果是0，那么我们就可以确信上文的NAND运算电路的输出也是对的。 有人可能会问，上文限制取值的多项式只能限制一个输入，但是我们有两个输入，如何同时限制他们的取值范围呢？其实答案很简单， 只需要把同样的多项式复制一份，两者加起来就好了。 有了这两个电路之后，我们只要确定约束电路的输出是0，那么NAND门电路就会正常运转了。 有一点需要注意的是，因为我们的逻辑门是从运算门搭建起来的，我们会发现其实逻辑运算非常的慢：任何逻辑运算至少得做一次乘法，然而熟悉计算机硬件的朋友们会知道，乘法其实是相对来说比较昂贵的运算。这样一来有一点颠倒黑白的感觉，在计算机里逻辑运算是最便宜也是最简单的计算，然而在数学运算电路里，逻辑运算反而是一个比较繁琐的过程了。 第三步：转换为可证明数学运算电路 当我们有了数字运算电路这个概念之后，我们就可以把不同的电路模块拼接起来，生成一个可以用作证明的运算电路出来。 首先，我们先定义一下可以用作证明的数字运算电路C(x, w)，具体构造如下： 简单的来说，这个电路C有两组输入。 第一组输入标记为x，我们称之为公有输入（public input），也就是说所有人都会知道x的值。这个x一般来说表达了想要证明的问题的特性和一些固定的环境变量。 第二组输入标记为w，我们称之为私密输入（secret input），或者又称之为witness。这一组数据就是真正提交证明的一方的谜底，只有证明的一方才会知道，其他人是不可以得之的。 当我们有C这一个电路之后，我们的目标就是证明C(x, w) = 0。换句话来说，在A和B已知数学运算电路C输出为0，并且公有输入为x的情况下，A需要证明她知道能够构成这个输出的私密输入值w。 如果我们把这个C(x, w)的概念代入上文提到的NAND门的例子里，我们会发现，光是NAND门不足以成为一个用做证明的电路。我们可以重新定义一下我们想证明的问题：**如果我们已知一个NAND门的输出为0，并且其中的一个输入Inp0为1，A想证明她知道另一个输入Inp1的值。**这个证明的过程中，不仅要保证NAND门的输出是对的，而且要保证所有的输入值都取值在我们事先约定好的区间内。 我们结合上面讨论的方案，把NAND的电路输出和我们的取值约束电路接在一起拼接成运算电路C，x为Inp0，w为Inp1，输出我们约束为0，从而构成一个完整的NAND门私密输入证明体系。 当我们得到最后的证明电路C之后，我们可以计算出这个运算电路的复杂度。 如果我们想知道一个数字运算电路C有多难算的时候，我们可以用里面有多少个运算门来描述它的复杂度。一般来说我们会用 $\mid C \mid$ 来表示。像是上面提到的NAND证明电路，$ \mid C \mid $大概是在10左右。…

浅谈零知识证明：背景与起源 作者：东泽 上个学期在斯坦福跟着Dan Boneh学习了区块链和数字货币相关的技术。和以往的课程不同的是，今年的课程新添加了一个章节，叫做零知识证明。萌萌的Dan和他的大神phd Ben Fisch给我们轮流上课，花了两周时间讲完了零知识的起源、概念和zkSNARK的实现。 这两天考完期末考试，复习的过程中在脑海中再三回味整堂课，觉得最精彩的部分还是零知识证明。想着最近趁着假期总结一下，分享给大家。 前言 写完第一稿之后，分享给朋友Proofread的时候，发现很多朋友反馈到说，背景知识不太够。所以我在开始之前额外添加了这一章节，标注了一下为了能读懂这篇文章所需的背景阅读： Merkle Tree/Merkle Proof: https://blog.csdn.net/wo541075754/article/details/54632929 比特币的交易: https://blog.csdn.net/liduanwh/article/details/81141972 UTXO模型: https://www.jianshu.com/p/02fd289e8853 一些基本的加密解密概念: https://www.jianshu.com/p/f7c729a41c9f 读完了前言之后，我们就可以开始正文了。 要说零知识证明真正火热的出现在大家的视野里，其实还要从比特币开始说起。 比特币的不足 如果熟悉比特币的话，大家应该会知道，在比特币网络上，每一笔交易都是公开的。 如果A要付给B一笔钱，那么A就会拿着大喇叭向全网公布，她要创建一笔新的交易（Tx），并且这个交易的受益人是B的公钥（P2PK），或者是公钥的哈希值（P2PKH）。B只要看到了这笔交易，就可以用自己的私钥签署一份数字签名，证明自己真的是这个公钥的主人，从而花掉这笔钱。 当A提交了付钱给B的这笔交易后，作为一个网络上的旁观者M，她只能看到一串乱码地址aaaaa要付x个币给一串乱码地址bbbbb。随后当B再打钱给C的时候，他也只能看到bbbbb打了一笔钱给ccccc。我们可以看到比特币里的交易是有很强的连接性的。虽然不知道谁打钱给了谁，但是我们可以顺藤摸瓜找到很多条交易链条。 如果每个用户都只是乖巧的来回打钱，比特币其实还是比较安全的。 一旦有用户看破了，不想玩了，想去交易所套现了，那么这一整条链的交易信息都会被暴露。交易所往往都有KYC（Know Your Customer）政策，每个数字货币和法币进行兑换的用户要进行实名制认证。一旦C从ccccc这个地址提款跑路了，那么交易所就掌握了bbbbb曾经打钱给C的事实。如果C涉嫌洗钱，这个时候只需要静静等待B套现出来，然后一把抓住。 美国现在已经有很多公司在做比特币上的交易链条分析，比如Chainalysis。 想必说到这里，大家都能感受到比特币的不足了：随机生成的收款公钥只是一个假象（网名），一旦在哪里实名制认证了，把网名和实名联系起来了，那么之前在网上所有的所作所为也就一览无余，毫无隐私可言。这就好比有人用网名在贴吧上发帖子喷人，然后被人用密保找到了手机号，再用手机号找到了注册的实名，从而被人肉是一个道理。 匿名（Anonymous） 与假名（Pseudonymous） 我们对于隐私的理解，其实分两种。 第一种是匿名（Anonymous），意思是用户不用透露任何和自己相关的信息，好比是学校的表白墙，你永远无法知道到底是谁写了上去，反正字就是写在了上面。 第二种是假名（Pseudonymous），意思是用户通过自己创造的假名来发表信息，好比是贴吧，如果你不了解这个用户，你无法建立网名到实名的联系，你也就不知道发帖的人是谁。 这么分析一看，比特币其实是一种假名机制：每个用户都会随机生成自己的公钥（假名），并且通过公钥地址来收款。这就好比是A/B/C/D四个人分别化名为小明/小红/二狗/小刚在网上匿名交易，只要D一旦在任何一个环节暴露出了自己的身份（比如在交易所提现），那么小明/小红/二狗和D之间的关系就会马上暴露出来。 我们对于如何增强比特币的保密性，可以从这两种方法来讨论。 增加隐秘性的方法 CoinJoin 既然A给B付钱会被人看到，C给D付钱也会被人看到，有人就想到了说那索性把ABCD这四个人全部扔到一笔交易里面去。因为比特币的交易可以多个输入输出，所以一个旁观者会看到一个交易里，aaaaa和ccccc都往里面打了x个币，然后bbbbb和ddddd收款。这样一来，就算交易所得知了这几个地址分别对应ABCD四人，也很难分辨到底谁收了谁的钱。 如果两组交易还是太好辨认怎么办？两个不够混四个，四个不够混八个，以此类推。把各种人的交易结合在一起，混淆视听，让人无法追踪。这就是CoinJoin。 CoinJoin的弊端是什么？其实混合多笔交易并不能完美的杜绝被人顺藤摸瓜，只能说在概率上减低了被一路摸上来的几率。而且还有一个很重要的一点，如果要混合AB与CD的交易，那么他们的交易量一定要相同。如果A付给B一万个币，C付给D一个币，我们只需要看输入和输出，就可以马上把一笔CoinJoin交易拆散成两个独立的交易。所以混搭相似交易额度的交易，也是CoinJoin在实现的时候一个不容忽视的难点。 如果用上文的分类来看的话，CoinJoin只是比特币现有系统的一个骚操作，它的本质仍然是假名机制。 Confidential Transaction（私密交易/CT） 既然隐藏我是谁那么麻烦，那么人们就开始动脑思考：如果不隐藏参与交易的公钥，我们还可以隐藏交易的额度。A给B打钱的时候，就算B被暴露了，全网也不会得知A究竟给了B多少钱。 如果这步操作能实现，那么我们甚至就可以用比特币发工资了，大家只能看到你每个月工资到账，但是并不知道你赚了多少钱。 想要具体实现的方法，我们先要了解一种特殊的加密算法：同态加密。 一句话概括的话，同态加密就是一种特殊的加密算法，可以让密文保持原有的数学特性。 我们可以假设有一个加密方法E，如果E是加法同态的话，那么E(a) + E(b) = E(a+b)。反之如果乘法同态的话，那么E(a) x E(b) = E(a x b)。 介于这篇文章是讲zkp的科普文，我们就不详细了解具体实现的方法了。我们只需要了解，椭圆加密方程和RSA里的大数模组都有某种同态的特性。 Pederson Commitment （Pederson承诺） 继续回到隐藏交易量的话题。如果A有100个币的余额，付10个币给B，那么这笔交易大概长这样： 结合上文提到的加法同态，如果我们有一个加法同态的加密方法E，我们就可以把这笔交易转化成： 只要第一个数等于后两个数之和，一个旁观者到头来也不会看到交易量，但是又不得不承认A真的分了一部分钱给B，然后还有一部分钱又退回给了A。这个方法叫做Pederson Commitment（Pederson承诺），隐藏了数据本身，但是证明了数据的关系。 负数漏洞 读到这里，有些朋友就会发现一个天大的漏洞：虽然Pederson承诺证明了数字之间的关系，但是并没有限制任何数字的取值区间！那也就说，A就可以使坏，提交一笔交易，说自己要付-100个币给B，然后“找”给自己200个币，这样一来一去，等式还是成立的。A就可以借此无限印钞，从而摧毁整个系统。…