Intro to the PKP Problem.

Bitcoin? def mine_btc(block): while True: nonce = random.randbytes(32) if hashlib.sha256(block + nonce).digest().hex()[:8] == "00000000": print("I'm rich!") return Or maybe some $\mathcal{math}$ helps: $$ e = mc^2$$…

iO入门04：基于GGH15构造多线性配对 写在前面 自从上一篇讨论【GGH+13】以来，不知不觉的已经过去了三个多月。几个月没有更新，不是笔者偷懒了，而是前一阵子在学算法和量子计算，课业太重实在无力写作。上周，这个学期刚刚结课，我们来补全$ \mathcal{iO} $系列的第四篇文章：构造多线性配对。 对于Multilinear Map这一密码学构造，我们在$ \mathcal{iO} $系列的前面三篇文章都有所提到过，这是一个比起FHE更有灵活性的密码学协议。FHE虽然强大，但是弱点在于它的安全性确保了FHE无法暴露出任何与密文有关的信息。而我们在进行混淆的时候，需要把被混淆的程序作为密文保存下来，但是得需要变相的在保证密文本身不泄漏的情况下计算这个程序。而多线性配对恰恰给了我们这一点自由度，在一个完美的加密系统中打了一个小孔，使得我们可以变相的来进行密文程序运算。 今天，我们就来看一看较为经典的MMAP构造：【GGH15】Graph Induced Multilinear Maps from Lattices，出于Gentry，Gorbunov与Halevi之手。 P.S. 本篇文章主要启发于Yilei Chen大神的讲座。 重温LWE问题 如果从之前的文章一路看来，想必大家对LWE问题已经非常不陌生了。在开始学习GGH15之前，我们需要重新回顾一下LWE问题的定义，并且引出一个新的变种来方便我们完成多线性配对的构造。 如上图所示，一个经典的LWE问题的定义中，一般包含了四个元素：代表LWE问题实例的$ \mathbf{A} $矩阵，代表“密钥”的$ \mathbf{s} $向量，代表噪音的$ \mathbf{e} $向量，以及最后通过线性结合得到的$ \mathbf{b} $向量。在Computational LWE问题中，我们要试图通过$ (\mathbf{A, b}) $这一对矩阵来试图求解出最初的密钥向量$ \mathbf{s} $来。而在Decisional LWE中，我们需要判断看到的这一对矩阵究竟是代表一个LWE问题实例，还是一个根据平均概率分布抽取的随机矩阵。 了解了LWE的经典定义之后，我们可以基于它的矩阵结构，进一步扩展（堆积）LWE中的$ \mathbf{s} $向量，使其从一个私密向量变成了一个私密矩阵。同理，我们也需要增加$ \mathbf{e} $以及$ \mathbf{b} $的维度，使得等式成立。如果LWE问题是困难的，那么这个新的形式的LWE问题仍然是困难的。因为我们可以把$ \mathbf{B, S, E} $矩阵的每行拆分开来（变成$ k $行），和原本的$ \mathbf{A} $矩阵就可以分别组合成$ k $个单独的LWE问题了。 我们在讨论经典LWE问题的时候，一般都是随机的生成$ \mathbf{s} $向量，平均随机（uniform random）的生成$ \mathbf{A} $矩阵，但是从一个限定噪声区间$ \mathbf{x}_B $中随机生成$ \mathbf{e} $向量。然而，在【ACPS09】中，Applebaum，Cash，Peikert与Sahai证明了其实如果我们从噪声区间中生成$ \mathbf{s} $的话，所构成的LWE问题的难度仍然不变。详细的对于这一发现的解读我们在这里就不多描述了，不过熟悉SIS问题的话想必就不会陌生：就算是猜一个二进制的私密向量$ \mathbf{s} \in {0,1}^n $，其实都是一个很困难的事情。 Idea：使用LWE来实现多线性配对 我们知道，一个简单的$ k $阶的多线性配对的构造大致如下： $$ g, g^{s_1}, g^{s_2}, \dots, g^{s_k} \rightarrow g_T^{\prod s_i} $$ 这也就是说，我们分别在循环群$ g $中encode了$ s_1, s_2, \dots, s_k $这$ k $个元素。而$ k $阶的多线性配对恰好可以帮助我们把这些encoding全部都“积攒”在一块儿，得到$ s_1 \cdot s_2 \cdot \dots \cdot s_k $的乘积在群$ g_T $中的encoding。…

iO入门03：从MBP开始构建多线性拼图 写在前面 上一期，我们一起看到了【GGH+13】中提出的Multilinear Jigsaw Puzzle大致上是什么个思路。 通过多线性配对这一神奇的工具，我们可以在不知道具体内容的情况下，直接在encoding上“同态计算”多线性配对算法$ e $，最后得到一个在目标group $ \mathbb{G}_T $中的计算结果。 这一工具搭配Barrington‘s Theorem中介绍的矩阵分叉程序（MBP），我们就可以计算未知的MBP程序了。 上图是我们上一期结束时所构成的对于$ \mathcal{iO} $的第一次尝试：$ \mathcal{iO}_{MBP} $。大致思路如下： 首先，把我们想要混淆的电路$ C $转换成MBP程序$ P = {\mathbf{inp}(i),\mathbf{M}_{i,b}} $。 随后，我们把这个MBP程序的矩阵部分$ {\mathbf{M}_{i,b}} $encode成多线性配对中的group element，得到$ {\mathbf{g}i^{\mathbf{M}{i,b}}} $。并且我们额外的计算在目标group中的单位矩阵的encoding $ \mathbf{g}_T^{\mathbf{I}_5} $。 最后，我们输出这一系列生成的元素作为电路$ C $的混淆：$ {\mathbf{inp}(i),\mathbf{g}T^{\mathbf{M}{i,b}}}, \mathbf{g}_T^{\mathbf{I}_5} $。 如果我们要计算输入$ x $对应的输出的话，那么我们就选择对应的encoding，根据MBP的计算方法使用Multilinear Map的$ \mathbf{e} $算法来进行矩阵相乘，最后得到在target group中计算结果的encoding。随后，我们在这个结果的encoding中减去$ \mathbf{I}5 $的encoding，就可以使用$ \mathbf{ZeroTest} $来完成计算： $$ C(x) = 0 \iff \mathbf{ZeroTest}(\mathbf{g}T^{\prod \mathbf{M}{i, x{\mathbf{inp}(i)}} - \mathbf{I}_5}) = 0 $$ 在达到正确性（correctness）之后，接下来我们的目标是达到$ \mathcal{iO} $所要求的安全性。 第一个问题：MBP矩阵的不可区分性 我们在上一期结束的时候，已经提到了我们现在的构造$ \mathcal{iO}_{MBP} $的最大问题：因为多线性配对encoding中并不包含randomness，每个encoding都和它的原文保持着紧紧的关联性。…

iO入门02：基于多线性配对的iO构造：多线性拼图（Multilinear Jigsaw Puzzle） 写在前面 距离上一期介绍$ \mathcal{iO} $之后又过去了很长的时间。在这段时间里，笔者工作和学习略忙就没怎么来得及写新的文章。同时笔者也在疯狂的补习$ \mathcal{iO} $这一方面的paper，为了写的文章内容的正确性，纵览了上下十多年的学术研究。希望这篇文章能够对于想要学习了解$ \mathcal{iO} $的读者们带来一定的帮助！ 我们在上期回顾$ \mathcal{iO} $的历史的时候讲到过，自从Barak et. al.在【BGI+01】中提出了$ \mathcal{iO} $这个构想之后，一直到2013年，才由Garg et. al.在【GGH+13】中提出了第一个较为有信服力的$ \mathcal{iO} $构造（Candidate）。【GGH+13】的$ \mathcal{iO} $构造依赖于一种同样在2013年被刚刚提出的多线性配对（Multilinear Map）这一构造所带来的一系列特性。正因如此，很大一部分程度上，【GGH+13】的$ \mathcal{iO} $构造的安全性依赖于它所用的多线性配对的安全性上。我们在上期的时候也稍微提到过，现有的很多Multilinear Map的构造如【GGH13】、【CLT13】以及【GGH15】都存在一些潜在的漏洞，有的甚至已经被完全攻破了。 好在，【GGH+13】仅仅是把多线性配对作为一个包装好的工具来直接使用，即只需要Multilinear Map对应的一系列算法的黑盒访问（Oracle Access），并不需要关心Multilinear Map具体的实现方法。这一点确保了，即使我们攻破了原有的Multilinear Map构造，我们也可以构造出新的替换上去，继续使得【GGH+13】保持原有的安全性。 我们上期在最后也提到了，自从多线性配对的概念被提出了之后，整个学术界就进入了一系列的攻防战，戏称Break-and-Repair Cycle。这是因为之前提出的构造多多少少还是存在了一些小的安全问题，而这些问题就会被特定的Cryptanalysis（密码分析）攻击所指定，随后攻破多线性配对的安全性。这就是为什么现在学术圈更加倾向于假设更清晰、构造更简单的新一代$ \mathcal{iO} $的构造，如上期最后提到的今年得到突破性发展的【JLS20】以及【BDGM20】等等。 虽说如此，笔者还是觉得一圈看下来，【GGH+13】的$ \mathcal{iO} $构造可以说是非常优雅、高效的设计。虽说它依靠了多线性配对这一非常不寻常（nontrivial）的构造假设，但是藏在整个构造背后的巧妙设计还是非常吸引人的。 话不多说，我们这一期就来深刻的学习一波【GGH+13】的$ \mathcal{iO} $构造吧！ P.S. 秉承深入浅出的概念，这一期我们只学习多线性配对的概念，但是并不讨论它的构造。因为【GGH+13】并不需要关心到它的具体结构，我们只需要知道如何调用多线性配对实现$ \mathcal{iO} $的目的即可。下一期我们再深入了解Multilinear Map中的【GGH15】构造。 $ \mathcal{iO} $与全同态加密（FHE） 在我们进入长篇大论的讨论多线性配对以及具体构造的正文之前，我们不妨稍作休息，来重温一遍当年构造出【GGH+13】的这帮大佬们当时的研究思路。 我们把时间退回到2013年初。这个时候，距离Gentry在【Gen09】提出FHE的可能性以及Bootstrapping的概念才过去了4年不到的时间。紧接着Gentry的发现，学术界投入了大量的经历开始研究更加高效实用的FHE构造。在这个领域比较有代表性的研究者有Brakerski，Vaikuntanathan，Gorbunov，Halevi，Sahai，Waters等等。 当FHE的概念大红大火的时候，一部分的研究者们把目光聚集到了尘封了12年依旧的【BGI+01】对于Indistinguishability Obfuscation的畅想上。在此之前，大家都没有想出来要怎么构造这么一个可以“混淆”别的算法的这么一个机制。然而，当我们拥有FHE之后，这一切变得不一样了。 FHE提出的概念，无疑就是我们可以在我们不知道内容的密文上同态的计算任何的函数$ f $，并且最后可以得到正确的运算结果（的密文形态）。 光是这个概念，就非常的具有混淆的味道。很多人一下子就想到了一个idea：如果我们把想要混淆的电路$ C $的描述作为密文放入到FHE的密文中，然后基于FHE的密文我们可以同态计算内嵌了输入$ x $的Universal Circuit（全能电路）$ U_x $。 全能电路这一概念我们在之前的文章中有所提到过，大致来说$ U(C, x) $是一个万能的电路，其功能如下：我们输入一个电路$ C $的描述，与$ C $的输入$ x $，然后全能电路就可以计算这个输入的电路在$ x $上的值$ U(C, x) = C(x) $随后输出。 $$ U(C, x) = C(x)\ U_x(C) = C(x) $$ 为了方便同态计算，我们在这里把输入的$ x $值“嵌入”到$ U $当中，构成只有一个输入的全能电路$ U_x $。这样，我们在FHE加密的电路描述$ C $上计算$ U_x $，就可以得到这个电路的输出结果即$ C(x) $了！…

iO入门01：什么是iO（Indistinguishability Obfuscation） 写在前面 千呼万唤始出来，我们终于要讲到格密码学最令人激动的话题——$ \mathcal{iO} $了！ $ \mathcal{iO} $，全名为Indistinguishability Obfuscation，中文大概译作不可区分混淆，是密码学中一种非常近似于黑科技一样的存在。如果$ \mathcal{iO} $真的存在的话，那么我们的整个数字世界都会为止发生改变。 $ \mathcal{iO} $又被称为是Crypto-complete（密码学完备）的。这是因为如果真的存在$ \mathcal{iO} $的话，我们可以基于$ \mathcal{iO} $构建出几乎所有的密码学构造：从公钥加密，到Functional Encryption（函数加密），Watermarking（数字水印），Multiparty Key Agreement（多方公钥交换），Deniable Encryption（可否认加密）等等的十分酷炫的密码学构造，都可以基于$ \mathcal{iO} $来实现。 这也就是说，如果我们能够实现$ \mathcal{iO} $的话，那我们几乎就可以放下其他密码学的假设和体系，单纯的使用$ \mathcal{iO} $就可以构造出一切的密码学应用。接下来需要做的就只是不停的优化和加固$ \mathcal{iO} $的构造就行了。 带着对$ \mathcal{iO} $的浓厚兴趣，笔者在今年暑假的时候深度的探索学习了一下$ \mathcal{iO} $的历史和现状。听了不少talk以及啃了不少篇paper之后，感觉对于$ \mathcal{iO} $的现状有了一个大概的了解，于是打算写下来再一次巩固对于这个专题的知识。 这一期，我们来看看$ \mathcal{iO} $是从哪里来，以及它究竟是一个什么样的概念。 从程序混淆（Software Obfuscation）开始 要想知道Indistinguishability Obfuscation是什么，我们不妨先来看一看Obfuscation是什么。 我们都知道，作为程序员，最宝贵的自然是我们写的代码了。一旦我们写的源码被人看到了，那么基本上花的心血和知识产权都被人一览无余。假如我们写了个画面非常精美，性能也很好的一款游戏，并且卖出去也买的很好，但是一卖出去就被人给反编译拿到源码了的话，那么第二年也许就会有无数第三方的游戏开发者直接copy我们的技术，并且做出跟我们差不多的游戏。 那么为了让我们写的程序卖出去之后不被人能够发现到底背后藏了些什么秘密（比如说非常强大的算法，或者是很聪明的数据结构等等），我们在导出程序准备卖出去之前可以采取一些手段来混淆（obfuscate）我们写的程序，在维持原本相同的功能性的同时，即使我们写的程序被人拿到了，别人也没有办法非常有效的把它还原成源代码，把我们辛辛苦苦积累的秘密全部拿走。 一般来说，我们现在会使用的程序混淆方法有两种。 代码混淆（Code Obfuscation） 在我们写程序的时候，往往都会根据实际的使用场景给变量或者函数命名。比如说一个计算下一秒展示的图像的函数，我们可以起名为calculate_next_frame()。一个代表UI控制器的变量，我们可以起名为ui_controller，等等。如果被别人看到了一段这样的代码，那么别人一下子就可以看明白这段程序到底在做什么。 于是，为了防止让我们的程序本身给外人提供太多的信息（以及使得程序的运转效率变得更高），我们会在导出程序的时候，把这些标注性的符号（symbols）统统的摘除掉。比较简单的实现方法是直接全文替换关键词，比如说把整段代码中所有的ui_controller全部替换成a0123456，这样一来，程序的symbols本身就无法暴露关于程序运转的内容了。 这一类的代码混淆器（Obfuscator）当今市面上很多，比如webpack就会在导出JavaScript至production的时候，自动的使用minify的功能来简化（并且混淆）JS代码。在我们编译Java与Kotlin程序（如安卓开发）的时候，同样我们可以使用ProGuard来进行代码的缩减和混淆化操作。 代码编译（Compilation） 第二种方法更加简单：我们直接输出编译过后的代码（可执行文件），这样别人就没法直接打开这个文件看到原本的代码了。 为什么编译之后的代码不会暴露出原本的源码信息呢？这是因为编译器在把人可以看的懂的源代码转换成电脑可以看得懂的机器码的这个过程中，就等于是把我们上面描述过的symbols全部去除了。同时，由于现代的Compiler都可以通过大量的代码优化（Optimization），比如Loop Unrolling（循环展开）等等的方法来改变代码的结构，使得最后生成的机器码和我们原本写的代码大相径庭。虽然说编译器的主要任务并不是用于混淆我们的代码，但是它通过把我们熟悉的代码转换成我们比较陌生的机器码的形式，变相的让我们对于同样的程序变得”不认识“了。 所以当别人看到我们发布的可执行文件中的机器码的时候，只会是一脸懵逼的啦。 对人的混淆并不是严格意义上的混淆 比较可惜的是，我们刚刚提到的当今常用的这两种方法，其实并不能作为真正意义上的混淆。 这是为什么呢？这是因为我们在做的事情，在密码学的定义上是非常脆弱的。这就像是上世纪二战的时候，我们通过各种各样的暗号以及暗码来加密通讯的电报，然后在另一头通过某一本小说或者报纸来解读出原文一样。整个系统的目的就在我们使用各种乱码一样的名字，错综复杂的逻辑结构（比如循环展开），以及不同的表述方式（把C变成汇编），尽可能使得看到我们最终混淆输出的人无法从输出中有效的提取和源代码有关的信息来。 char*M,A,Z,E=40,J[40],T[40];main(C){for(*J=A=scanf(M="%d",&C); -- E; J[ E] =T [E ]= E) printf(".…

格密码学进阶09：基于GSW的NIZK（下） 上期回顾 上期，我们看到了【KW17】中基于GSW的NIZK构造。大概的构造思路是基于GSW全同态加密（FHE）的变种，即全同态承诺（FHC）。 基于GSW FHC，Prover可以把要证明NP Relation的witness $ w $的承诺发送给Verifier，然后Verifier基于承诺$ c_w $同态计算证明电路$ C_x(\cdot) $。最后，Prover提供一个opening，可以让Verifier打开计算之后的结果，看到电路的输出。如果$ C_x(w) = 0 $，那么代表witness有效，证明也就通过了。 在上期的最后，我们也看到了【KW17】的NIZK的构造，虽然基于FHC的idea很有意思，但是也有两个缺陷。一个是同态承诺的opening $ \mathbf{R}_{C_x, w} $在概率分布上会暴露出和$ w $有关的信息。另一个更大的问题是，如果Prover没有遵守协议，并没有一开始诚实的发送一个GSW FHC的承诺$ c_w $的话， 那么整个协议就失去了意义，毫无Soundness可言。 这期，我们就来着重的看看如何解决这两大问题，最后得到【KW17】的完全构造～ Soundness的问题 首先，我们来看看如何解决最大的问题，即Soundness的问题。 我们知道，如果Prover并不会诚实的构造GSW FHC承诺的话，那么整个协议就会失去所有的可信度。但是比较头疼的是，我们并没有一个非常好的方法来“证明”Prover发送给Verifier承诺$ c $真的是基于witness $ w $诚实构造的GSW FHC承诺。最好的证明方法就是直接把$ w $发送过去，但是这违背了我们原本零知识的要求。 我们在上期的结尾也稍微讨论过，还有一种可能性就是Prover可以事先零知识地证明他所公开的承诺是一个诚实构造的GSW FHC承诺。如果使用了别的NIZK方案，那肯定会变相的基于其他方案中的假设。但是由于我们在这里就是在尝试构造纯粹基于Lattice假设的零知识证明，所以这种方法并不可取。 从NIZK到Preprocessing NIZK 乍一看，似乎我们已经束手无策了，没有办法通过GSW FHC来构造真正的NIZK。 因为真正的NIZK要求过于苛刻，Prover没有办法说服Verifier他发送的承诺是诚实的，所以我们现在卡在了这个点上无法继续下去。既然如此，我们可不可以放松对于NIZK的要求，使得我们可以绕过这个问题呢？ 一个最简单的放松（relaxation）版本，就是Preprocessing NIZK，即加入一个预处理（Preprocessing）的阶段。在Preprocessing的阶段，一个协议的双方（即Prover与Verifier）可以委托一个可信的第三方（Trusted Third Party，TTP）进行一系列诚实的参数生成操作。 在参数生成阶段完成之后，TTP会把生成的参数分为两组：属于Prover的参数$ k_p $，与属于Verifier的参数$ k_v $。最后，TTP会把这两组参数秘密的发送给Prover与Verifier。在整个初始化的阶段中，Prover和Verifier都可以完全相信TTP生成的参数是诚实生成的，不会有任何造假的部分。 对于这一类由TTP生成参数并且发送给协议双方的结构，我们称之为Trusted Setup（可信初始化）。对于zkSNARK以及隐私货币技术比较熟悉的读者们可能对于这个定义并不陌生，我们在这里就不多描述了。 我们还可以把TTP做的部分替换成一个MPC协议来完成。因为协议双方完全信赖TTP，并且TTP也不会作假，这一要求和MPC能带给我们的非常相似。这样的话，Prover与Verifier只需要在协议的一开始进行一次MPC，就可以相互得到对应的初始化参数$ k_p, k_v $了。 基于Preprocessing Model的第一次尝试 当我们relax了对于NIZK的定义，采用了Preprocessing Model之后，相比起原来的NIZK规定，我们额外的多拥有了一次可信初始化的机会。 即然我们之前遇到的问题在于Prover没法证明他生成的承诺是可信的（诚实的），那我们索性缺啥补啥：直接在可信初始化阶段生成证明所需要的承诺$ c_w $。…

格密码学进阶08：基于GSW的NIZK（上） 写在前面 经过了漫长的铺垫，我们终于可以来正式的学习基于格的第一个较为酷炫的应用：非交互零知识证明（Non-Interactive Zero-Knowledge proofs，NIZK）。 去年12月份的时候，笔者开始写【浅谈零知识证明】这个专题，花了挺大的篇幅大概描述了zkSNARK，一个用在ZCash中并且基于LPCP的零知识证明体系。如果对于零知识证明这一概念还比较陌生的话，不妨再去回顾一下之前的这个专题～ 这一次，我们来看一个完全不一样的NIZK构造方案。 P.S. 本文主要描述了Kim与Wu的paper【KW17】：Multi-theorem Preprocessing NIZKs from Lattices。 NIZK的快速回顾 在开始之前，我们不妨先快速的回顾一下NIZK的定义。在一个零知识证明系统中，需要有证明方（Prover）与验证方（Verifier）。在这个协议中，Prover会生成一个证明（Proof），并且试图说服（convince）Verifier某些信息。通常来说，我们会使用NIZK来“证明”一些特定的信息。比如说，我们想要证明我们知道某个问题的解，但是并不想暴露这个解本身。 NIZK分为两部分，NI（非交互）与ZK（零知识）。 非交互这一部分很简单，要求证明方要一次性的（one-shot）生成一个Proof，发送给Verifier，随后Verifier验证收到的证明，输出验证结果，不能再有额外的interaction。对于某些符合要求的交互性协议（比如$ \Sigma $协议），我们可以通过Fiat-Shamir来压缩成非交互协议。 零知识的定义要更为复杂一点，要求在整个协议执行时双方生成的任何交互（transcript）信息的概率分布能够被一个simulator（模拟器）来生成。当一个协议满足了ZK的条件之后，我们光看它的transcript，无法有效的分辨这个transcript到底是来自于真正的协议，还是来自于模拟器。这个特点带来的好处就是，协议的transcript无法暴露任何未公开的信息。一个零知识协议的tanscript就算公开出去，也没有有效的adversary可以还原出任何有用的信息。 关于零知识证明，还有几点经常会讨论到的属性。 Correctness Correctness即正确性，主要规定了如果Prover是诚实的（Honest），真的知道想要证明的信息本身的话，那么Verifier一定会（或者绝大几率会）接受Prover生成的Proof。 Soundness Soundness即健全性，主要约束了如果Prover是恶意的（Malicious），随便编造了一个Proof出来，那么Verifier会有相对来说比较小的几率接受这个Proof。一般来说，这个几率不需要太小，因为我们可以通过反复的iterate这个Verify的步骤来把这个几率不断的缩小，直到变成negligible。 Proof of Knowledge（PoK） 比较有意思的一个属性是PoK，即知识证明。这个属性代表了我们的这个零知识证明的Prover，一定需要”知道“一些内容才行。这个内容，一般写作$ w $（witness），可能是某个问题的解，或者是某个特殊的relation，甚至是几个数字都可以。最关键的一点要在于，我们需要”证明“这个协议中的Prover真的”知道“这些内容。 为了证明PoK，我们需要对于一个交互协议构造出一个对应的Extractor（提取器）。这个Extractor可以充当Verifier的角色，任意的跟协议中的Prover进行交互。同时，它还拥有时间回溯的特异功能，可以在看到Prover的Proof之后，马上时间回溯到协议的开始，再进行不同的交互。如果Extractor可以通过多次不同的交互的transcript有效的“提取”出Prover想要证明的信息$ w $的话，那么代表这个协议满足了PoK的属性。 一般来说，除了在分析协议的时候我们会看PoK这个属性之外，我们在构造新的协议的时候，也需要想着怎么把这个Extractor“埋进”这个协议当中，使得任何人只要通过多次交互，就可以提取出witness。在正常使用协议的情况下，PoK的属性并不会对于安全性有任何影响。这是因为在一次协议中Prover不会和Verifier进行多次交互。 我们可以把PoK看作一个更加严格的Soundness属性。Soundness规定了，如果不知道witness，那么无法通过验证。PoK规定了，就算Prover知道了witness，也需要能够被Extractor提取出来才行。 Honest-Verifier Zero-Knowledge（HVZK） 最后一个就是Zero-Knowledge了，具体的定义和我们之前讨论的相同，即整个协议的transcript不能泄漏任何有用的信息，甚至它的概率分布可以直接被模拟出来。 在分析零知识协议的时候，我们一般都会假设Prover可能会是恶意的（Malicious），即Prover有动机去做假，就算没有witness，也会试图convince Verifier使其相信他拥有正确的witness。一个协议的soundness有效的避免了Malicious的Prover。不过我们不会对于Verifier作出太多的要求，所以一般来说我们都会假设Verifier会诚实的遵守整个协议（Honest Verifier）。 HVZK的属性说明了，当Verifier是诚实的，而Prover可以是诚实或者是恶意的情况下，Verifier无法从transcript中提取出任何与witness相关的信息，甚至可以通过一个simulator来模拟整个transcript。 NIZK的证明结构 如果之前了解过zkSNARK一类的SNARK零知识证明的话，肯定会对于零知识证明中证明的结构有一定的认知：我们会有一个电路$ C $与公共参数$ x $，Prover需要证明他拥有一个witness $ w $使得电路满足$ C(x, w) = 0 $。这样的构造是一个非常常见的零知识证明framework，即我们把证明的内容变成了一个电路，然后我们证明的是我们知道某个输入会导致这个电路计算出的结果为0。 当然了，NIZK的范畴不仅仅是我们提到的这些。像是Schnorr protocol等等的$ \Sigma $协议，都可以被转换为NIZK，然而这些协议中所“证明”的内容和结构也大不相同。我们在这里关心的NIZK，主要是为了证明Prover知道一个NP问题的解（Proof of NP Relation）。 如果要再严谨一点的话，我们这里讨论的Prover，需要证明某个问题实例$ x $属于一个问题集合L中，而这个问题集合L又属于NP： $$ x \in L\ L \in NP $$ L属于NP，这意味着存在一组关系集合$ R_L $，任何在L中的实例$ x’ $都在$ R_L $中拥有对应的witness： $$ x’ \in L \iff \exists w’ \text{ s.…

格密码学进阶07：GSW同态体系的Key Equation 写在前面 GSW即Gentry-Sahai-Waters全同态加密系统。在我的另一个专题【初探全同态证明】中，已经用了两三篇的篇幅详细介绍过GSW同态加密体系的原理与构造了。 然而在这里，我们重新回顾一下GSW的构造，并且探索一些除了FHE之外，GSW特有的新特性。这些特性对于我们探索后期的应用非常重要。 P.S. 本文主要内容均来自于Hoeteck Wee的一个FHE tutorial，其中用到的图片都来自于原文。 GSW同态加密体系回顾 我们熟悉的FHE（全同态加密）系统，主要的属性分为两点：同态与加密。 其中，同态这一特性为整个系统的功能性（functionality），因为它可以同态的计算密文中的内容，得到新的密文，使得我们完成一定的功能。然而加密这一特性为安全性（security），因为它确保了密文中隐藏的原文不会被提取出来。 我们这里跟随之前类似的视角，先从功能性开始回顾GSW。 Homomorphic Functionality FHE的functionality属性，如果简单的概括的话，就是我们可以通过$ x $的密文$ ct_x $同态计算某个function $ f $，然后得到： $$ ct_{f(x)} = Eval(pk, ct_x) $$ 其中$ f $可以是任何复杂度与功能性的函数。 如果只考虑这一特性，我们可以在一开始找到一个很简单的例子：矩阵的特征值（eigenvalue）与特征向量（eigenvector）。 我们假设这个系统中的“密钥”$ sk $是向量$ \mathbf{t} $。假如我们要加密某个值$ x_i $，我们只需要找到一个对应的矩阵$ \mathbf{A}_i $使得： $$ \mathbf{t} \cdot \mathbf{A}_i = x_i \mathbf{t} $$ 这里的$ \mathbf{A}_i $就是密文了。我们可以很简单的发现，我们可以很简单的把不同的$ \mathbf{A}_i $组合起来，同态计算其中的原文： $$ \begin{align*} \text{Add} &: \mathbf{t} \cdot (\mathbf{A}_1 + \mathbf{A}_2) = (x_1 + x_2) \mathbf{t}\ \text{Mult} &: \mathbf{t} \cdot (\mathbf{A}_1\mathbf{A}_2) = x_1x_2 \mathbf{t}\ \text{Polynomial} &: \mathbf{t} \cdot (\mathbf{A}_1\mathbf{A}_2 + \mathbf{A}_3\mathbf{A}_4) = (x_1x_2 + x_3x_4) \mathbf{t} \end{align*} $$ 如果我们总结一下这种表达形式的话，我们可以把要计算的部分用$ f $来代替： $$ \mathbf{t} \cdot \underbrace{f(\mathbf{A}_1, \dots, \mathbf{A}n)}{\mathbf{A}_f} = f(x_1, \dots, x_n) \mathbf{t} $$ 等式的左侧是我们直接通过密文$ \mathbf{A}_i $结合生成的同态计算结果$ \mathbf{A}_f $，而等式的右侧就是直接在原文上计算$ f $的结果。注意在这里，我们使用$ \mathbf{A} $矩阵来表示密文，而不是平常会用到的$ C $，这样的notation和之前稍微不同。…

Lattice ABE的大致结构 上一期我们看到了【AFV11】的内积ABE的构造。在AFV11中，密文中带有向量$ \mathbf{x} $，而解密者拥有向量$ \mathbf{y} $。如果$ \langle \mathbf{x, y} \rangle = 0 $，那么解密者就可以成功的用他的密钥解开密文。 在上期最后，我们给出了基于格的ABE属性加密的大致结构。我们一共需要三个部分： 首先，我们需要把要加密的原文$ \mu $使用一组随机选择生成的One-Time Pad $ \mathbf{u}^t \mathbf{s} $覆盖住： $$ C = \mathbf{u}^t \mathbf{s} + noise + \mu $$ 这里的$ \mathbf{u} $是公开的，而$ \mathbf{s} $与$ noise $都是加密方自己随机生成的。 随后，解密的目的就在于计算出近似$ \mathbf{u}^t \mathbf{s} $的值，然后就可以从$ C $中移除这个OTP，进而还原出$ \mu $。我们目前先把这个密文放在一边，来构造属性密文。我们想要把加密方选择的属性输入变相的encode在密文当中。假设属性输入为一系列的二进制向量$ \mathbf{x} \in \mathbb{Z}_2^n $，我们根据每一个输入构建一个对应的密文： $$ C_i = (\mathbf{A}_i + \mathbf{x}_i \mathbf{G})^t \mathbf{s} + \mathbf{noise} $$ 其中$ \mathbf{A}_i $是事先公开生成的，而$ \mathbf{s} $与$ \mathbf{noise} $都是加密方选择的，其中$ \mathbf{s} $的值需要和之前的一致。…