一个C米通信gydF4y2Ba

研究突出了gydF4y2Ba

匹诺曹:几乎实用的可验证计算gydF4y2Ba

布莱恩·帕诺，乔恩·豪厄尔，克雷格·金特里，玛丽安娜·瑞科娃gydF4y2Ba
ACM通信，2016年2月，第59卷第2期，第103-112页gydF4y2Ba
10.1145 / 2856449gydF4y2Ba
评论gydF4y2Ba

为了给外包给云计算的计算注入更大的信心，客户应该能够这样做gydF4y2Ba验证gydF4y2Ba返回结果的正确性。为此，我们引入了一种名为Pinocchio的系统，它可以在仅依赖密码假设的情况下有效地验证一般计算。对于匹诺曹，客户端创建一个公共评估密钥来描述她的计算;这种设置与计算计算一次成正比。然后，工作者对特定输入的计算进行评估，并使用评估键来产生正确性的证明。无论执行的计算或IO的大小如何，证明都只有288字节。任何人都可以使用公开验证密钥检查证明。gydF4y2Ba

至关重要的是，我们对7个应用程序的评估表明，在实践中，Pinocchio也是有效的。匹诺曹的验证时间是固定的10毫秒加上每个IO元素0.415秒:比以前的工作少57个数量级gydF4y2Ba^23gydF4y2Ba；的确，对于某些应用程序来说，Pinocchio是第一个证明验证比本地执行更便宜的通用系统。工人的证明工作仍然是昂贵的，但与之前的工作相比，皮诺奇减少了19×60×。作为一个附加特性，Pinocchio允许工作人员在计算中包含私有输入，并证明她正确地执行了计算，而不向客户机透露任何关于私有输入的信息。最后，为了帮助开发，Pinocchio提供了一个端到端工具链，它将C的一个子集编译成实现可验证计算协议的程序。gydF4y2Ba

回到顶部gydF4y2Ba

1.简介gydF4y2Ba

由于计算能力通常是不对称的(特别是对于移动设备)，相对较弱的客户机可能希望将计算外包给一个或多个强大的工作者。例如，科学家可能想要在云中运行蛋白质折叠模拟，或者利用志愿者的分布式计算。在这样的设置中，客户端应该能够gydF4y2Ba验证gydF4y2Ba结果返回，以防止恶意或故障的工人。即使从合法工作者的角度来看，可验证的结果也是有益的，因为它们可能要价更高。它们还允许工作者摆脱责任:任何不希望的输出都可以证明是客户提供的数据的结果。gydF4y2Ba

大量的系统和理论研究已经关注了验证计算的问题(第6节)。然而，大多数工作要么是特定于函数的，依赖于我们宁愿避免的假设，要么就是无法通过基本的实用性要求。功能特定的解决方案gydF4y2Ba^{13gydF4y2Ba，gydF4y2Ba24gydF4y2Ba}通常是有效的，但只适用于一小类计算。更通用的解决方案往往依赖于可能不适用的假设。例如，基于复制的系统gydF4y2Ba^5gydF4y2Ba假设不相关的故障，而基于可信计算的故障gydF4y2Ba^19gydF4y2Ba或其他安全硬件gydF4y2Ba^16gydF4y2Ba假设物理保护不能被击败。最后，理论界已经产生了许多漂亮的、通用的协议gydF4y2Ba^{1gydF4y2Ba，gydF4y2Ba9gydF4y2Ba，gydF4y2Ba12gydF4y2Ba，gydF4y2Ba15gydF4y2Ba}这提供了令人信服的渐近性。然而，在实践中，因为许多依赖于复杂的概率可检证明(pcp)gydF4y2Ba^1gydF4y2Ba或完全同态加密(FHE)，gydF4y2Ba^11gydF4y2Ba目前的性能是不可接受的，利用小实例将需要数百万年(第5.1节)。最近的工作gydF4y2Ba^{7gydF4y2Ba，gydF4y2Ba22gydF4y2Ba，gydF4y2Ba23gydF4y2Ba}已经大大改进了这些协议，但效率仍然存在问题，协议缺乏公共验证等功能。在没有公开验证的情况下，任何能够验证证明的人也可以提供作弊证明。gydF4y2Ba

相比之下，匹诺曹是一个具体的系统，它可以有效地验证一般计算，同时只进行密码假设。特别是，匹诺曹支持公共可验证计算(VC)，gydF4y2Ba^{9gydF4y2Ba，gydF4y2Ba20.gydF4y2Ba}让一个不被信任的工人去生产gydF4y2Ba计算签名。gydF4y2Ba最初，客户端选择一个函数并生成一个公共评估密钥和一个(小的)公共验证密钥。给定计算键，工作人员可验证地计算输入上的函数，并生成一个证明(或签名)来伴随结果。任何人(不仅仅是客户端)都可以使用验证键来检查工作者使用的特定输入的结果的正确性。gydF4y2Ba

作为一个附加特性，Pinocchio支持零知识VC，在这种情况下，工作者使客户机相信它知道一个或多个具有特定属性的私有输入，而不透露有关输入的任何信息。例如，食品储藏室gydF4y2Ba^4gydF4y2Ba使用匹诺曹对服务器持有的私有数据(例如，DMV照片)计算Map-Reduce作业(例如，图像匹配)。最近的工作还使用匹诺曹来匿名化比特币交易，在完全不知情的情况下证明交易不会创造或摧毁货币。gydF4y2Ba^{2gydF4y2Ba，gydF4y2Ba8gydF4y2Ba}

皮诺曹的渐近性非常好:密钥设置和证明生成所需的密码操作在原始计算的大小上是线性的，而验证所需的时间在输入和输出的大小上是线性的。更令人惊讶的是，皮诺曹的证据是恒定大小的，gydF4y2Ba不管gydF4y2Ba所执行的计算。至关重要的是，我们的计算(第5节)证明了这些渐近性伴随着小常数。gydF4y2Ba

与之前的工作相比，gydF4y2Ba^23gydF4y2Ba匹诺曹将验证时间缩短了57秒gydF4y2Ba数量级gydF4y2Ba对于IO大小合理的应用程序，需要不到10毫秒的时间，这使得对于某些应用程序，Pinocchio可以击败原生C执行。我们还通过19×60×相对于之前的工作改进了工作者的证明工作。结果证明非常小，只有288字节(只比RSA-2048签名略多一点)，不管计算如何。制作零知识证明也很便宜，增加的开销可以忽略不计(密钥生成的开销为213秒，证明生成的开销为0.1%)。gydF4y2Ba

虽然这些改进是有希望的，但在工人证明开销达到真正的实用性之前，还需要额外的进展。然而，即使是现在，这种开销在需要高度保证或需要匹诺曹支持的零知识属性的场景中也是可以接受的。gydF4y2Ba

为了实现高效的VC，皮诺曹结合gydF4y2Ba二次计划,gydF4y2BaGennaro等人引入的计算模型，gydF4y2Ba^10gydF4y2Ba通过一系列的理论改进和系统工程来产生一个端到端工具链来验证计算。具体来说，通过相对于Gennaro等人改进的协议和证明技术，我们将密钥生成成本降低了61%，生成证明的成本降低了64%。从开发人员的角度来看，Pinocchio提供了一个编译器，它可以将C代码转换为电路表示(我们同时支持布尔和算术)，将电路转换为二次程序，然后生成程序来执行加密协议(gydF4y2Ba图1gydF4y2Ba)．gydF4y2Ba

Pinocchio的端到端工具链允许我们实现从验证中受益的实际应用程序。特别地，我们实现了两种形式的矩阵乘法，多元多项式评估，图像匹配，全对最短路径，一个格-气体科学模拟器和SHA-1。我们发现(第5节)，前三个应用程序可以有效地转换为算术电路，因此，与本地执行相同程序相比，Pinocchio可以更快地验证它们的结果。后四种应用程序的翻译效率较低，因为它们依赖于不等式比较和位运算，但它们对于零知识应用程序可能仍然有用。gydF4y2Ba

综上所述，本文贡献如下:gydF4y2Ba

1. 一种端到端系统，用于有效地验证由一个或多个不受信任的工作者执行的计算。这包括一个将C代码转换为适合验证的格式的编译器，以及一套用于运行实际协议的工具。gydF4y2Ba
2. 与之前的工作相比，理论和系统层面的改进使性能下降了57个数量级，gydF4y2Ba^23gydF4y2Ba因此进入了似是而非的领域。gydF4y2Ba
3. 对7个真正的C应用程序的评估，显示验证速度比某些应用程序的32位本机整数执行快。gydF4y2Ba

回到顶部gydF4y2Ba

2.背景gydF4y2Ba

2.1.可验证计算(VC)gydF4y2Ba

公共VC方案允许计算量有限的客户机将函数的计算工作外包给工作者gydF4y2BaFgydF4y2Ba在输入gydF4y2BaugydF4y2Ba．然后，客户端可以验证返回结果的正确性gydF4y2BaFgydF4y2Ba（gydF4y2BaugydF4y2Ba)，同时执行比函数评估所需的工作量更少的工作。gydF4y2Ba

更正式地，我们将公共VC定义为如下，概括了以前的定义。gydF4y2Ba^{9gydF4y2Ba，gydF4y2Ba10gydF4y2Ba，gydF4y2Ba20.gydF4y2Ba}

定义1(公共可验证计算)。gydF4y2Ba公共可验证计算方案V C由三种多项式时间算法组成gydF4y2Ba（gydF4y2BaKeyGen，计算，验证gydF4y2Ba):

• （gydF4y2Ba埃克gydF4y2Ba_FgydF4y2Ba、VKgydF4y2Ba_FgydF4y2Ba)gydF4y2Ba注册机gydF4y2Ba（gydF4y2BaFgydF4y2Ba， 1gydF4y2Ba):随机密钥生成算法取被外包函数F和安全参数;它输出一个公共评估密钥EKgydF4y2Ba_FgydF4y2Ba，公钥VKgydF4y2Ba_FgydF4y2Ba．gydF4y2Ba
• （gydF4y2Bay,gydF4y2Ba_ygydF4y2Ba)gydF4y2Ba计算gydF4y2Ba（gydF4y2Ba埃克gydF4y2Ba_FgydF4y2Ba,你gydF4y2Ba)gydF4y2Ba:确定性工作者算法使用公共评估密钥EKgydF4y2Ba_FgydF4y2Ba输入u，输出y F(u)和一个证明gydF4y2Ba_ygydF4y2Ba， y的正确性gydF4y2Ba．gydF4y2Ba
• {0,1}gydF4y2Ba验证gydF4y2Ba（gydF4y2BaVKgydF4y2Ba_FgydF4y2Ba， u, y，gydF4y2Ba_ygydF4y2Ba)gydF4y2Ba:给定验证密钥VKgydF4y2Ba_fgydF4y2Ba，确定性验证算法在FgydF4y2Ba（gydF4y2BaugydF4y2Ba) =gydF4y2BaY，否则为0gydF4y2Ba．gydF4y2Ba

之前的工作给出了正确性、安全性和效率的正式定义，gydF4y2Ba^10gydF4y2Ba所以我们只总结一下:gydF4y2Ba

• 正确性gydF4y2Ba．对于任何函数gydF4y2BaFgydF4y2Ba，以及任何输入gydF4y2BaugydF4y2Ba来gydF4y2BaFgydF4y2Ba，如果我们生成的键gydF4y2BaFgydF4y2Ba，然后跑gydF4y2Ba计算gydF4y2Ba使用得到的评估键gydF4y2Ba埃克gydF4y2Ba_fgydF4y2Ba,然后gydF4y2Ba验证gydF4y2Ba将永远接受。gydF4y2Ba
• 安全gydF4y2Ba．对于任何函数gydF4y2BaFgydF4y2Ba和任何概率多项式时间对手，对手不能提供IO的证明gydF4y2Bau,gydF4y2Ba这样gydF4y2BaFgydF4y2Ba（gydF4y2BaugydF4y2Ba)gydF4y2Ba但gydF4y2Ba验证gydF4y2Ba接受证明。gydF4y2Ba
• 效率gydF4y2Ba．gydF4y2Ba注册机gydF4y2Ba假设是一个一次性操作，其代价在多次计算中摊销，但我们要求gydF4y2Ba验证gydF4y2Ba比F的值便宜。gydF4y2Ba

之前的几个风险投资计划gydF4y2Ba^9gydF4y2Ba不是公开的，而是gydF4y2Ba指定的验证者,gydF4y2Ba意思是验证密钥gydF4y2BaVKgydF4y2Ba_FgydF4y2Ba必须保密。实际上，在这些方案中，即使是暴露验证函数的输出(例如，是否发现工作者作弊)也可能导致对系统的攻击。公共风险投资计划避免了这些问题。gydF4y2Ba

零知识可验证计算gydF4y2Ba．我们还考虑了一个扩展设置，其中外包计算是一个函数，gydF4y2BaFgydF4y2Ba（gydF4y2Bau,gydF4y2BawgydF4y2Ba)，两个输入:客户的输入gydF4y2BaugydF4y2Ba还有一个辅助输入gydF4y2BawgydF4y2Ba从工人那里。VC方案是gydF4y2Ba0知识gydF4y2Ba如果客户机除了计算的输出之外，对工作者的输入一无所知。gydF4y2Ba

2.2.二次程序gydF4y2Ba

Gennaro, Gentry, Parno和Raykova (GGPR)展示了如何将计算编码为二次程序，gydF4y2Ba^10gydF4y2Ba从而得到有效的VC和零知识VC方案。具体来说，他们展示了如何将任何算术电路转换为一个相当大小的二次算术程序(QAP)。gydF4y2Ba

标准结果表明，多项式大小的电路与运行时间为多项式的图灵机是等价的(直到对数因子)，当然，通过电路与本地硬件的实际计算效率在很大程度上取决于应用程序;例如，用于矩阵乘法的算术电路基本上不会增加任何开销，而用于整数乘法的布尔电路的效率远远低于执行一条32位汇编指令。gydF4y2Ba

算术电路由携带字段值的导线组成gydF4y2Ba并连接到加法和乘法门gydF4y2Ba图2gydF4y2Ba举个例子。gydF4y2Ba

在正式定义qap之前，我们先介绍对电路进行编码的步骤gydF4y2Ba图2gydF4y2Ba变成一个等效的QAP。首先，我们选择两个任意值，gydF4y2BargydF4y2Ba_5gydF4y2Ba，gydF4y2BargydF4y2Ba_6gydF4y2Ba表示两个乘法门(加法门将被压缩到它们对乘法门的贡献中)。我们定义了三组多项式gydF4y2BaVgydF4y2Ba，gydF4y2BaWgydF4y2Ba,gydF4y2BaYgydF4y2Ba通过引入多项式gydF4y2BaVgydF4y2Ba将左侧输入编码到每个乘法门中gydF4y2BaWgydF4y2Ba将正确的输入编码到每个门，然后gydF4y2BaYgydF4y2Ba对输出编码。因此，对于电路在gydF4y2Ba图2gydF4y2Ba，我们为每个集合定义6个多项式gydF4y2BaVgydF4y2Ba，gydF4y2BaWgydF4y2Ba,gydF4y2BaY,gydF4y2Ba四个是输入线，两个是乘法门的输出。我们根据每根导线对乘法门的贡献来定义这些多项式。特别是所有的gydF4y2BavgydF4y2Ba_kgydF4y2Ba（gydF4y2BargydF4y2Ba_5gydF4y2Ba) = 0，除gydF4y2BavgydF4y2Ba_3.gydF4y2Ba（gydF4y2BargydF4y2Ba_5gydF4y2Ba) = 1，因为第三条输入线贡献了的左输入gydF4y2BacgydF4y2Ba_5gydF4y2Ba乘法门。同样的,gydF4y2BavgydF4y2Ba_kgydF4y2Ba（gydF4y2BargydF4y2Ba_6gydF4y2Ba) = 0，除了gydF4y2BavgydF4y2Ba_1gydF4y2Ba（gydF4y2BargydF4y2Ba_6gydF4y2Ba) =gydF4y2BavgydF4y2Ba_2gydF4y2Ba（gydF4y2BargydF4y2Ba_6gydF4y2Ba) = 1，因为前两个输入都贡献给的左输入gydF4y2BacgydF4y2Ba_6gydF4y2Ba的门。为gydF4y2BaWgydF4y2Ba，我们看正确的输入。最后,gydF4y2BaYgydF4y2Ba代表输出;没有一根输入线是输出线，所以gydF4y2BaygydF4y2Ba_kgydF4y2Ba（gydF4y2BargydF4y2Ba_5gydF4y2Ba) =gydF4y2BaygydF4y2Ba_kgydF4y2Ba（gydF4y2BargydF4y2Ba_6gydF4y2Ba) = 0gydF4y2BakgydF4y2Ba{1,……，4}，而且gydF4y2BaygydF4y2Ba_5gydF4y2Ba（gydF4y2BargydF4y2Ba_5gydF4y2Ba) =gydF4y2BaygydF4y2Ba_6gydF4y2Ba（gydF4y2BargydF4y2Ba_6gydF4y2Ba) = 1。正如我们下面解释的那样，我们可以使用这种电路编码来有效地检查它是否被正确地求值。gydF4y2Ba

更一般地，我们定义QAP，一种算术电路的编码，如下所示。gydF4y2Ba

定义2(二次算术程序(qap)gydF4y2Ba^10gydF4y2Ba)．gydF4y2Ba一个QAP Q在场上gydF4y2Ba包含三组mgydF4y2Ba+ 1gydF4y2Ba多项式VgydF4y2Ba= {gydF4y2BavgydF4y2Ba_kgydF4y2Ba(x)gydF4y2Ba}，gydF4y2BaWgydF4y2Ba= {gydF4y2BawgydF4y2Ba_kgydF4y2Ba(x)gydF4y2Ba}，gydF4y2BaYgydF4y2Ba= {gydF4y2BaygydF4y2Ba_kgydF4y2Ba(x)gydF4y2Ba}，gydF4y2BakgydF4y2Ba｛gydF4y2Ba0…M}，目标多项式t(x)。假设F是一个函数，它的n个元素是gydF4y2Ba输出n'元素，总共n = n + n' I/O元素。然后我们说Q计算F如果:(cgydF4y2Ba_1gydF4y2Ba,……cgydF4y2Ba_NgydF4y2Ba)gydF4y2Ba^NgydF4y2Ba是F的输入和输出的有效赋值，当且仅当存在系数(cgydF4y2Ba_{NgydF4y2Ba＋1gydF4y2Ba},……cgydF4y2Ba_米gydF4y2Ba)使t(x)除p(x)，其中:gydF4y2Ba

换句话说，一定存在某个多项式h(x)使得h(x)·t(x) = p(x)Q的大小是m，度是t(x)的度gydF4y2Ba．gydF4y2Ba

建立质量保证程序gydF4y2Ba问gydF4y2Ba用于一般的算术电路gydF4y2BaCgydF4y2Ba是相当直接的。我们取一个任意根gydF4y2BargydF4y2Ba_ggydF4y2Ba对于每个乘法门gydF4y2BaggydF4y2Ba在gydF4y2BaCgydF4y2Ba定义目标多项式为gydF4y2BatgydF4y2Ba（gydF4y2BaxgydF4y2Ba) =gydF4y2Ba_ggydF4y2Ba（gydF4y2BaxgydF4y2BargydF4y2Ba_ggydF4y2Ba)．我们关联一个索引gydF4y2BakgydF4y2Ba［gydF4y2Ba米gydF4y2Ba={1…gydF4y2Ba米gydF4y2Ba}到电路的每个输入端和乘法门的每个输出端。最后，我们定义多项式gydF4y2BaVgydF4y2Ba，gydF4y2BaWgydF4y2Ba,gydF4y2BaYgydF4y2Ba通过引入多项式gydF4y2BaVgydF4y2Ba将左侧输入编码到每个门中gydF4y2BaWgydF4y2Ba将正确的输入编码到每个门，然后gydF4y2BaYgydF4y2Ba对输出编码。例如,gydF4y2BavgydF4y2Ba_kgydF4y2Ba（gydF4y2BargydF4y2Ba_ggydF4y2Ba= 1gydF4y2BakgydF4y2Ba这条线是门的左输入gydF4y2BaggydF4y2Ba,gydF4y2BavgydF4y2Ba_kgydF4y2Ba（gydF4y2BargydF4y2Ba_ggydF4y2Ba)否则= 0。同样的,gydF4y2BaygydF4y2Ba_kgydF4y2Ba（gydF4y2BargydF4y2Ba_ggydF4y2Ba= 1gydF4y2BakgydF4y2Ba这条线是栅极的输出gydF4y2BaggydF4y2Ba,gydF4y2BaygydF4y2Ba_kgydF4y2Ba（gydF4y2BargydF4y2Ba_ggydF4y2Ba)否则= 0。因此，如果我们考虑一个特定的门gydF4y2BaggydF4y2Ba它的根gydF4y2BargydF4y2Ba_ggydF4y2Ba，式(1)化简为:gydF4y2Ba它的意思是，门的输出值等于输入值的乘积，这就是乘法门的定义。例如，在QAP的电路中gydF4y2Ba图2gydF4y2Ba，如果我们计算gydF4y2BapgydF4y2Ba（gydF4y2BaxgydF4y2Ba)gydF4y2BargydF4y2Ba_5gydF4y2Ba，我们得到(gydF4y2BacgydF4y2Ba_3.gydF4y2Ba·(gydF4y2BacgydF4y2Ba_4gydF4y2Ba) =gydF4y2BacgydF4y2Ba_5gydF4y2Ba，它直接编码第一个乘法门，类似地，在gydF4y2BargydF4y2Ba_6gydF4y2Ba，gydF4y2BapgydF4y2Ba（gydF4y2BaxgydF4y2Ba)化简为(gydF4y2BacgydF4y2Ba_1gydF4y2Ba+gydF4y2BacgydF4y2Ba_2gydF4y2Ba·(gydF4y2BacgydF4y2Ba_5gydF4y2Ba) =gydF4y2BacgydF4y2Ba_6gydF4y2Ba，即第二乘法门的编码。gydF4y2Ba

简而言之，可除性检验gydF4y2BatgydF4y2Ba（gydF4y2BaxgydF4y2Ba)分gydF4y2BapgydF4y2Ba（gydF4y2BaxgydF4y2Ba)分解为deg(gydF4y2BatgydF4y2Ba（gydF4y2BaxgydF4y2Ba每个门各一张gydF4y2BaggydF4y2Ba和根gydF4y2BargydF4y2Ba_ggydF4y2Ba的gydF4y2BatgydF4y2Ba（gydF4y2BaxgydF4y2Ba),gydF4y2BapgydF4y2Ba（gydF4y2BargydF4y2Ba_ggydF4y2Ba) = 0。gydF4y2Ba

实际施工gydF4y2Ba^10gydF4y2Ba有点复杂，因为它处理常量的加法和乘法。尽管如此，GGPR表明，对于任何算术电路gydF4y2BadgydF4y2Ba乘法门和gydF4y2BaNgydF4y2BaI/O元素，可以用度(根的数量)构造一个等价的QAPgydF4y2BargydF4y2Ba_ggydF4y2Ba)gydF4y2BadgydF4y2Ba和大小(每个集合中多项式的个数)gydF4y2BadgydF4y2Ba+gydF4y2BaNgydF4y2Ba．注意，加法门和常数乘法门并不影响QAP的大小或程度。因此，在基于qap的VC方案中，这些门基本上是“免费的”。gydF4y2Ba

强QAPsgydF4y2Ba．在他们基于QAP的VC方案中，GGPR不幸地需要来自QAP的强属性，如下所述。注意定义2只考虑相同系数集的情况gydF4y2BacgydF4y2Ba_我gydF4y2Ba应用于所有三组多项式。GGPR还要求定义2中的if- only-if条件即使在不同系数时也保持不变gydF4y2Ba一个gydF4y2Ba_我gydF4y2Ba，gydF4y2BabgydF4y2Ba_我gydF4y2Ba，gydF4y2BacgydF4y2Ba_我gydF4y2Ba也就是说，什么时候适用gydF4y2Ba．他们展示了如何将任何QAP转换成gydF4y2BaQAP强gydF4y2Ba它满足更强的条件。不幸的是，这一强化步骤将QAP的程度增加到gydF4y2Ba3 dgydF4y2Ba+gydF4y2Ba2 n,gydF4y2Ba超过gydF4y2Ba三倍gydF4y2Ba它。这反过来又使密钥生成的成本、评估密钥的大小和工作人员生成证明的工作量增加了三倍以上。gydF4y2Ba

2.3.用二次程序构建VCgydF4y2Ba

要从一个二次元程序构造一个VC协议，我们需要映射每个多项式，例如，gydF4y2BavgydF4y2Ba_kgydF4y2Ba（gydF4y2BaxgydF4y2Ba)对一个元素的二次程序gydF4y2BaggydF4y2Ba^vgydF4y2BakgydF4y2Ba^{(年代)gydF4y2Ba}在椭圆曲线群中gydF4y2Ba，在那里gydF4y2Ba年代gydF4y2Ba客户机是否选择了一个秘密值，和gydF4y2BaggydF4y2Ba是一个生成器gydF4y2Ba．这些组元素被分配给工人。对于给定的输入，工作人员直接对电路进行评估，以获得输出和内部电路导线的值。这些值对应于系数gydF4y2BacgydF4y2Ba_我gydF4y2Ba二次程序。因此，VC工作者可以进行评估gydF4y2BavgydF4y2Ba（gydF4y2Ba年代gydF4y2Ba) =gydF4y2BakgydF4y2Ba［gydF4y2Ba米gydF4y2Ba］gydF4y2BacgydF4y2Ba_kgydF4y2Ba·gydF4y2BavgydF4y2Ba_kgydF4y2Ba（gydF4y2Ba年代gydF4y2Ba)"在指数中"得到gydF4y2BaggydF4y2Ba^{vgydF4y2Ba（gydF4y2Ba年代gydF4y2Ba)gydF4y2Ba}；它计算gydF4y2BawgydF4y2Ba（gydF4y2Ba年代gydF4y2Ba),gydF4y2BaygydF4y2Ba（gydF4y2Ba年代gydF4y2Ba)，在指数中，同理。gydF4y2Ba

为了让工人证明式(1)成立，我们还，作为评估关键的一部分，给工人gydF4y2Ba条款。工人计算gydF4y2Ba，然后使用gydF4y2BahgydF4y2Ba_我gydF4y2Ba，连同gydF4y2BaTer米年代，来计算ggydF4y2Ba^{hgydF4y2Ba（gydF4y2Ba年代gydF4y2Ba)gydF4y2Ba}．为了简化，证明由(gydF4y2BaggydF4y2Ba^{vgydF4y2Ba（gydF4y2Ba年代gydF4y2Ba)gydF4y2Ba}，gydF4y2BaggydF4y2Ba^{wgydF4y2Ba（gydF4y2Ba年代gydF4y2Ba)gydF4y2Ba}，gydF4y2BaggydF4y2Ba^{ygydF4y2Ba（gydF4y2Ba年代gydF4y2Ba)gydF4y2Ba}，gydF4y2BaggydF4y2Ba^{hgydF4y2Ba（gydF4y2Ba年代gydF4y2Ba)gydF4y2Ba})．验证一下gydF4y2BapgydF4y2Ba（gydF4y2Ba年代gydF4y2Ba) =gydF4y2BahgydF4y2Ba（gydF4y2Ba年代gydF4y2Ba)gydF4y2BatgydF4y2Ba（gydF4y2Ba年代gydF4y2Ba)，验证者使用gydF4y2Ba双线性映射gydF4y2Ba这允许他取两个椭圆曲线元素，并将它们的指数“相乘”，以创建一个新组中的元素。实际的协议gydF4y2Ba^10gydF4y2Ba是否有点复杂，因为需要额外的机制来确保工人包含客户机的输入gydF4y2BaugydF4y2Ba正确，而且工人确实生产(比如说)gydF4y2BavgydF4y2Ba（gydF4y2Ba年代gydF4y2Ba的某个线性函数gydF4y2BavgydF4y2Ba_kgydF4y2Ba（gydF4y2Ba年代gydF4y2Ba)的值。gydF4y2Ba

关于效率，GGPRgydF4y2Ba^10gydF4y2Ba说明一次性设置的gydF4y2Ba注册机gydF4y2Ba在原电路尺寸中按时间线性运行，gydF4y2BaOgydF4y2Ba(|gydF4y2BaCgydF4y2Ba|)。工人执行gydF4y2BaOgydF4y2Ba(|gydF4y2BaCgydF4y2Ba密码工作，但他也必须执行gydF4y2BaOgydF4y2Ba(|gydF4y2BaCgydF4y2Ba|日志gydF4y2Ba^2gydF4y2Ba|gydF4y2BaCgydF4y2Ba|)非加密工作计算gydF4y2Bah (x)gydF4y2Ba．为了实现这一性能，worker利用了这样一个事实:评估向量(gydF4y2BavgydF4y2Ba_kgydF4y2Ba（gydF4y2BargydF4y2Ba_1gydF4y2Ba),…gydF4y2BavgydF4y2Ba_kgydF4y2Ba（gydF4y2BargydF4y2Ba_dgydF4y2Ba)都非常稀疏(也用于gydF4y2BawgydF4y2Ba而且gydF4y2BaygydF4y2Ba多项式)。证明本身的大小是恒定的，qap只有9个组元素，尽管验证者的工作仍然是线性的，gydF4y2BaOgydF4y2Ba（gydF4y2BaNgydF4y2Ba)，即函数的输入和输出的大小。gydF4y2Ba

在安全方面，GGPRgydF4y2Ba^10gydF4y2Ba表明该VC方案是合理的gydF4y2BadgydF4y2Ba-PKE和gydF4y2Ba问gydF4y2Ba-PDH假设，这是之前工作中假设的弱版本。gydF4y2Ba

零知识。gydF4y2Ba使VC方案零知识是非常简单的。一个简单地包括目标多项式gydF4y2BatgydF4y2Ba（gydF4y2BaxgydF4y2Ba)在多项式集中gydF4y2BaVgydF4y2Ba，gydF4y2BaW,gydF4y2Ba而且gydF4y2BaY。gydF4y2Ba这允许工作人员通过添加“随机化”其证明gydF4y2Ba_vgydF4y2BatgydF4y2Ba（gydF4y2Ba年代gydF4y2Ba)的指数gydF4y2BavgydF4y2Ba_{中期gydF4y2Ba}（gydF4y2Ba年代gydF4y2Ba)gydF4y2Ba，gydF4y2Ba_wgydF4y2BatgydF4y2Ba（gydF4y2Ba年代gydF4y2Ba)gydF4y2BawgydF4y2Ba（gydF4y2Ba年代gydF4y2Ba),gydF4y2Ba_ygydF4y2BatgydF4y2Ba（gydF4y2Ba年代gydF4y2Ba)gydF4y2BaygydF4y2Ba（gydF4y2Ba年代gydF4y2Ba)gydF4y2Ba_vgydF4y2Ba，gydF4y2Ba_wgydF4y2Ba，gydF4y2Ba_ygydF4y2Ba，并相应地修改证明的其他要素。的修改值gydF4y2BapgydF4y2Ba（gydF4y2BaxgydF4y2Ba)仍然可以被整除gydF4y2BatgydF4y2Ba（gydF4y2BaxgydF4y2Ba)，但随机化使方案在统计上为零知识。gydF4y2Ba^10gydF4y2Ba

回到顶部gydF4y2Ba

3.理论细化gydF4y2Ba

在本节中，我们将改进GGPR协议gydF4y2Ba^10gydF4y2Ba显著减少密钥生成时间、评估密钥大小和工作人员的工作量。我们将在第5节中实证地分析我们的改进。gydF4y2Ba

我们的主要优化是我们构造了一个VC方案gydF4y2Ba常规的gydF4y2BaQAP(如定义2)，而不是gydF4y2Ba强大的gydF4y2BaQAP。回想一下GGPR展示了如何将常规QAP转换为强QAP，但是转换不止于此gydF4y2Ba三元组gydF4y2BaQAP的程度。因此，当它们将强QAP插入VC结构中时，强化步骤将使密钥生成时间、评估密钥大小和工作者计算增加两倍以上。我们采用了一种使用常规QAP的不同方法，因此我们根本不需要加强步骤。相反，我们在新的VC证明中嵌入了额外的结构，以确保工作者使用相同的线性组合来构造gydF4y2Bav, wgydF4y2Ba,gydF4y2BaygydF4y2Ba证明的术语。gydF4y2Ba^{一个gydF4y2Ba}令人惊讶的是，这个额外的结构是没有成本的，而我们的VC方案实际上是gydF4y2Ba少gydF4y2Ba比GGPR还要复杂!最后，我们通过设计一些针对特定功能的自定义电路门，扩展了qap所能计算的功能的表达能力和效率。gydF4y2Ba

3.1.我们新的VC协议gydF4y2Ba

接下来，我们描述了更高效的VC方案，并对它的一些性质进行了评述。gydF4y2Ba

协议1(从常规qap可验证的计算)。gydF4y2Ba

• (埃克gydF4y2Ba_FgydF4y2Ba、VKgydF4y2Ba_FgydF4y2Ba)gydF4y2Ba注册机gydF4y2Ba(FgydF4y2Ba， 1gydF4y2Ba):设F是一个有N个输入/输出值的函数gydF4y2Ba．将F转换成算术电路C;然后构建相应的QAP Q = (t(x)， V, W, Y)，大小为m，次数为dgydF4y2Ba_{中期gydF4y2Ba}= {gydF4y2BaN + 1，…,米gydF4y2Ba}，gydF4y2Ba即非io相关指标gydF4y2Ba．gydF4y2Ba
  设e为非平凡双线性映射e:gydF4y2BagydF4y2Ba×_TgydF4y2Ba设g是g的一个生成器gydF4y2Ba．gydF4y2Ba
  选择rgydF4y2Ba_vgydF4y2Ba, rgydF4y2Ba_wgydF4y2Ba年代,gydF4y2Ba_vgydF4y2Ba，gydF4y2Ba_wgydF4y2Ba，gydF4y2Ba_ygydF4y2Ba，，随机从gydF4y2Ba设rgydF4y2Ba_ygydF4y2Ba= rgydF4y2Ba_vgydF4y2Ba·rgydF4y2Ba_wgydF4y2BaggydF4y2Ba_vgydF4y2Ba= ggydF4y2Ba^{房车gydF4y2Ba}ggydF4y2Ba_wgydF4y2Ba= ggydF4y2Ba^rwgydF4y2Ba和ggydF4y2Ba_ygydF4y2Ba= ggydF4y2Ba^{变化中gydF4y2Ba}．gydF4y2Ba
  构建公众评价关键EKgydF4y2Ba_FgydF4y2Ba为:gydF4y2Ba
  
  
  
  公开验证密钥为:gydF4y2Ba
• (y,gydF4y2Ba_ygydF4y2Ba计算(EK)gydF4y2Ba_FgydF4y2Ba， u):在输入u上，工作者对电路F求值，得到y F(u);他也学会了价值观gydF4y2Ba电路的电线gydF4y2Ba．gydF4y2Ba
  他解出了h(x)(使p(x) = h(x)·t(x)的多项式)，并计算证明gydF4y2Ba_ygydF4y2Ba为:gydF4y2Ba
  
  
  
  在vgydF4y2Ba_{中期gydF4y2Ba}(x) = kIgydF4y2Ba_{中期gydF4y2Ba}cgydF4y2Ba_kgydF4y2Ba·vgydF4y2Ba_kgydF4y2Ba(x)， w也是如此gydF4y2Ba_{中期gydF4y2Ba}(s)和ygydF4y2Ba_{中期gydF4y2Ba}(s).由于这些都是线性方程，他可以使用评估键中的材料“在指数中”计算它们，例如，gydF4y2Ba．gydF4y2Ba
• {0,1}验证(VKgydF4y2Ba_FgydF4y2Ba， u, y，gydF4y2Ba_ygydF4y2Ba):对有要素的所谓证据的验证gydF4y2Ba，gydF4y2Ba和ggydF4y2Ba^ZgydF4y2Ba使用公共验证密钥VKgydF4y2Ba_FgydF4y2Ba配对函数e用于以下检查gydF4y2Ba．gydF4y2Ba
  • QAP的可除性检查:使用来自VK的元素gydF4y2Ba_FgydF4y2Ba，计算一项表示I/O, u和y，将它们表示为系数cgydF4y2Ba_1gydF4y2Ba,……cgydF4y2Ba_NgydF4y2Ba和计算:gydF4y2Ba（同理gydF4y2Ba而且gydF4y2Ba）．检查:gydF4y2Ba
    
    
    
    
  • 检查在V, W和Y上计算的线性组合是否在它们适当的张成空间中:gydF4y2Ba
    
    
  • 检查每一个关于V, W和Y的线性组合中使用了相同的系数:gydF4y2Ba
    
    
    
    在指定的验证者设置中(其中验证者知道s, a等)，对只需要用于可除性校验，并且I/O项可以直接计算gydF4y2Ba，而不是“in the exponent”。gydF4y2Ba

VC方案的正确性取决于QAP的性质。在安全方面，我们有以下几点:gydF4y2Ba

定理1。gydF4y2Ba设d为VC方案中QAP的程度的上限，设q =gydF4y2Ba4gydF4y2BadgydF4y2Ba+ 4。gydF4y2Ba在d-PKE、q-PDH和2q-SDH条件下，VC方案是合理的。gydF4y2Ba

定理1的证明见全文。gydF4y2Ba

安全的直觉。gydF4y2Ba作为为什么VC方案是健全的直觉，注意它似乎很难的对手谁不知道构建gydF4y2Ba任何gydF4y2Ba组元素对gydF4y2BahgydF4y2Ba，gydF4y2BahgydF4y2Ba除了gydF4y2Ba很明显，通过配对(gydF4y2BaggydF4y2Ba_1gydF4y2Ba，gydF4y2Ba),（gydF4y2gydF4y2BaBaggydF4y2Ba_2gydF4y2Ba，gydF4y2Ba),…他被给定，并应用相同的线性组合(在指数中)到对的左右元素。这种硬度在gydF4y2BadgydF4y2Ba-PKE假设，一种“指数知识”假设，它说对手必须“知道”这样的线性组合，从某种意义上说，这个线性组合可以从他那里提取。粗略地说，这意味着，在安全证明中，我们可以提取多项式gydF4y2BaVgydF4y2Ba_{中期gydF4y2Ba}（gydF4y2BaxgydF4y2Ba)，gydF4y2BaWgydF4y2Ba_{中期gydF4y2Ba}（gydF4y2BaxgydF4y2Ba)，gydF4y2BaYgydF4y2Ba_{中期gydF4y2Ba}（gydF4y2BaxgydF4y2Ba如:如此gydF4y2BaVgydF4y2Ba_{中期gydF4y2Ba}(由证明)等于gydF4y2BaVgydF4y2Ba_{中期gydF4y2Ba}（gydF4y2Ba年代gydF4y2Ba)，gydF4y2BaWgydF4y2Ba_{中期gydF4y2Ba}＝gydF4y2BaWgydF4y2Ba_{中期gydF4y2Ba}（gydF4y2Ba年代gydF4y2Ba),gydF4y2BaYgydF4y2Ba_{中期gydF4y2Ba}＝gydF4y2BaYgydF4y2Ba_{中期gydF4y2Ba}（gydF4y2Ba年代gydF4y2Ba)，而且这些多项式是在线性张成的gydF4y2BavgydF4y2Ba_kgydF4y2Ba（gydF4y2BaxgydF4y2Ba)的,gydF4y2BawgydF4y2Ba_kgydF4y2Ba（gydF4y2BaxgydF4y2Ba),gydF4y2BaygydF4y2Ba_kgydF4y2Ba（gydF4y2BaxgydF4y2Ba分别)。如果对手设法提供了一个验证错误陈述的证明，那么这些多项式一定不是实际对应的QAP解。所以,要么gydF4y2BapgydF4y2Ba（gydF4y2BaxgydF4y2Ba)不能被整除gydF4y2BatgydF4y2Ba（gydF4y2BaxgydF4y2Ba在这种情况下，我们破坏2gydF4y2Ba问gydF4y2Basdh)或gydF4y2BaVgydF4y2Ba（gydF4y2BaxgydF4y2Ba) =gydF4y2BavgydF4y2Ba_iogydF4y2Ba（gydF4y2BaxgydF4y2Ba) +gydF4y2BaVgydF4y2Ba_{中期gydF4y2Ba}（gydF4y2BaxgydF4y2Ba)gydF4y2BaWgydF4y2Ba（gydF4y2BaxgydF4y2Ba),gydF4y2BaYgydF4y2Ba（gydF4y2BaxgydF4y2Ba)不使用相同的线性组合(在这种情况下，我们打破gydF4y2Ba问gydF4y2Ba-PDH因为在证明中我们选择了一种聪明的方式)。gydF4y2Ba

零知识。gydF4y2Ba我们可以应用GGPR的重随机化技术gydF4y2Ba^10gydF4y2Ba(第2.3节)，为我们新的VC构建提供统计零知识。工人选择gydF4y2Ba_vgydF4y2Ba，gydF4y2Ba_wgydF4y2Ba，gydF4y2Ba_ygydF4y2Ba在他的证明中，不是多项式gydF4y2BavgydF4y2Ba_{中期gydF4y2Ba}（gydF4y2BaxgydF4y2Ba)，gydF4y2BavgydF4y2Ba（gydF4y2BaxgydF4y2Ba)，gydF4y2BawgydF4y2Ba（gydF4y2BaxgydF4y2Ba),gydF4y2BaygydF4y2Ba（gydF4y2BaxgydF4y2Ba)，他使用了以下的随机版本gydF4y2BavgydF4y2Ba_{中期gydF4y2Ba}（gydF4y2BaxgydF4y2Ba) +gydF4y2Ba_vgydF4y2BatgydF4y2Ba（gydF4y2BaxgydF4y2Ba)，gydF4y2BavgydF4y2Ba（gydF4y2BaxgydF4y2Ba) +gydF4y2Ba_vgydF4y2BatgydF4y2Ba（gydF4y2BaxgydF4y2Ba)，gydF4y2BawgydF4y2Ba（gydF4y2BaxgydF4y2Ba) +gydF4y2Ba_wgydF4y2BatgydF4y2Ba（gydF4y2BaxgydF4y2Ba),gydF4y2BaygydF4y2Ba（gydF4y2BaxgydF4y2Ba) +gydF4y2Ba_ygydF4y2BatgydF4y2Ba（gydF4y2BaxgydF4y2Ba)．gydF4y2Ba

的性能。gydF4y2Ba我们的主要改进是我们的VC方案只需要一个常规的QAP，而不是一个强QAP，这提高了超过3倍的性能。此外，该方案本身更简单，使得密钥和证明中的组元素更少，验证的双线性映射更少等。gydF4y2Ba

3.2.表达电路结构gydF4y2Ba

我们在VC方案中使用的QAP定义在gydF4y2Ba_pgydF4y2Ba,在那里gydF4y2BapgydF4y2Ba是一个大质数。正如前面所解释的，我们可以推导一个QAPgydF4y2Ba_pgydF4y2Ba它可以有效地计算任何函数gydF4y2BaFgydF4y2Ba可以用对p取模的加法和乘法来表示。这没有提供明显的方法来表示一些运算，例如gydF4y2Ba一个gydF4y2BabgydF4y2Ba使用mod -gydF4y2BapgydF4y2Ba算术。另一方面，给定gydF4y2Ba一个gydF4y2Ba而且gydF4y2BabgydF4y2Ba作为比特，比较很容易。因此，人们可能会推断布尔电路更为普遍。gydF4y2Ba

然而，我们设计了一个算法gydF4y2Ba分裂门gydF4y2Ba翻译算术线gydF4y2Ba一个gydF4y2Ba_pgydF4y2Ba，已知在[0,2gydF4y2Ba^kgydF4y2Ba1),gydF4y2BakgydF4y2Ba二进制输出线。给定这样的二进制值，我们可以使用算术门计算布尔函数:NAND(a, b) = 1gydF4y2Baab,gydF4y2Ba和(gydF4y2Ba一个gydF4y2Ba，gydF4y2BabgydF4y2Ba) =gydF4y2Baab,gydF4y2Ba或(gydF4y2Ba一个gydF4y2Ba，gydF4y2BabgydF4y2Ba) = 1 (1gydF4y2Ba一个gydF4y2Ba) (1gydF4y2BabgydF4y2Ba)．每个嵌入的布尔门只需要一次乘法。gydF4y2Ba

令人惊讶的是，这种算法嵌入给出了一个相当高效的VC格式。嵌入引入了一个昂贵的初始门，它将每个输入限制为{0,1}，但从今以后，每个嵌入门保持{0,1}不变，只对QAP的程度和大小增加1。此外，表达式gydF4y2Ba的位表示组合gydF4y2Ba一个gydF4y2Ba回到单线上。因为和由常数的加法和乘法组成，所以重组是自由的;它不会增加QAP的规模。gydF4y2Ba

在我们的整篇论文中，我们还设计了一个门来强制两根导线之间相等，以及一个门来检查一根导线是否等于零。这些可以组成(参考文献中的Thm 11)。gydF4y2Ba^10gydF4y2Ba)与其他大门。gydF4y2Ba

回到顶部gydF4y2Ba

4.实现gydF4y2Ba

我们实现了一个编译器，它将C语言的一个子集转换为一个等价的算术电路(第4.1节)。然后，我们的VC套件将电路表示编译到等效的QAP中，并生成运行VC协议的代码，包括密钥生成、证明计算和证明验证(章节4.2)。工具链编译大量的应用程序集合，并通过验证运行它们(第4.3节)。工具链的源代码是可用的。gydF4y2Ba^bgydF4y2Ba

4.1.编译器工具链gydF4y2Ba

下面描述的(第4.3节)和第5节评估的应用程序都是使用gydF4y2Ba手法gydF4y2Ba我们的c- to- algorithm -expression编译器，是一个3525行Python程序。它们也用gydF4y2Ba海湾合作委员会gydF4y2Ba产生当地的时间gydF4y2Ba图5gydF4y2Ba而且gydF4y2Ba6gydF4y2Ba．gydF4y2Ba

编译器可以理解C语言的一个重要子集，包括全局变量、函数变量和块作用域变量;数组、结构体和指针;函数调用、条件语句、循环;和静态初始化式(gydF4y2Ba图3gydF4y2Ba)．它还理解算术和位布尔运算符以及预处理器语法。gydF4y2Ba

由于“目标机器”(算术电路)只支持表达式，而不支持可变状态和迭代，因此我们相应地限制了C程序的语义。例如，指针和数组解引用必须是编译时常量;否则，每个动态引用将产生大小与可寻址内存成正比的条件表达式。函数调用是内联的，同时保留C变量作用域和指针语义。gydF4y2Ba

命令式条件编译为编码命令式副作用的条件表达式。静态条件在编译时分解。类似地，具有静态可计算终止条件的循环将自动完全展开。gydF4y2Ba

目前支持的惟一标量类型是gydF4y2BaintgydF4y2Ba；编译器标志选择整数大小。编译器插入屏蔽表达式以确保agydF4y2BakgydF4y2Ba-bit int的行为与相应的C类型完全相同，包括overflow。gydF4y2Ba

编译器的中间语言是一组类似c的运算符表达式，比如+、*、<=、?:、&和^。gydF4y2Ba

编译器后端将每个表达式展开为算术门语言mul、add、const-mul、wiresplit等，消除了常见的子表达式。它仔细地限制了每个线值的位宽:gydF4y2Ba

• 输入有编译器指定的gydF4y2BaintgydF4y2Ba宽度;gydF4y2Ba
• 每个常量都有一个已知的宽度(例如，13 = 1101)gydF4y2Ba_2gydF4y2Ba位宽4);gydF4y2Ba
• 位运算产生gydF4y2Ba马克斯gydF4y2Ba它的论点的宽度;gydF4y2Ba
• 添加可以产生gydF4y2Ba马克斯gydF4y2Ba+ 1位(进位);而且gydF4y2Ba
• 摩尔能产生2·gydF4y2Ba马克斯gydF4y2Ba位。gydF4y2Ba

当宽度接近字段中的可用位(254)时，编译器生成一个分割门，将值截断回指定的值gydF4y2BaintgydF4y2Ba宽度。跟踪位宽最大限度地降低了分闸的成本。gydF4y2Ba

4.2.二次程序与密码协议gydF4y2Ba

下一个管道阶段接受一个布尔或算术电路，并构建一个QSP或QAP(第2节)。然后，根据第3.1节，它将二次程序编译成一组用于客户端(密钥生成和验证)和工作者(计算和证明生成)的密码例程。为了进行比较，我们还实现了原始的GGPRgydF4y2Ba^10gydF4y2Ba；GGPR协议第5节说明了Pinocchio的增强减少了1864%的开销。gydF4y2Ba

密钥生成例程在客户端运行，具有可选择的公共验证和零知识特性(第5.2节)。代码通过网络将评估密钥传输给工作者;为了节省带宽，程序以C语言传输，工作者在本地编译。gydF4y2Ba

计算例程在服务器上运行，从客户端收集输入，使用计算键生成证明，并将证明传输回客户端(或者，如果需要，另一个验证者)。验证程序使用验证密钥和证明来确定工人是否作弊。gydF4y2Ba

我们的加密代码是单线程的，但每个阶段都是令人尴尬的并行。之前的工作gydF4y2Ba^23gydF4y2Ba表明标准技术可以跨核心、机器或gpu并行化工作。对于密码，我们使用高速椭圆曲线库gydF4y2Ba^18gydF4y2Ba256位的bn曲线提供128位的安全性。程序构造和协议执行的二次代码是10832行C和c++。gydF4y2Ba

快取幂。gydF4y2Ba生成评估键gydF4y2Ba埃克gydF4y2Ba需要对同底数取幂gydF4y2BaggydF4y2Ba对许多不同的力量。我们通过调整Pippenger的多指数算法来优化这一操作。本质上，这意味着我们建立一个中间幂的表gydF4y2BaggydF4y2Ba，让我们只需要做几次乘法就可以计算任何特定的指数。gydF4y2Ba

类似地，工人最大的开销来源是将“指数”中的电路系数应用到计算中gydF4y2BaggydF4y2Ba^{YgydF4y2Ba（gydF4y2Ba年代gydF4y2Ba)gydF4y2Ba}，gydF4y2Ba等。我们通过滑动窗口技术优化这一操作，为每对碱基建立一个小的幂表。在实践中，这些表可以将性能提高3到4倍，甚至将最初构建表的时间也计算在内。gydF4y2Ba

多项式渐近。gydF4y2Ba为了生成证明，工作者必须计算多项式gydF4y2BahgydF4y2Ba（gydF4y2BaxgydF4y2Ba如:如此gydF4y2BatgydF4y2Ba（gydF4y2BaxgydF4y2Ba)·gydF4y2BahgydF4y2Ba（gydF4y2BaxgydF4y2Ba) =gydF4y2BaPgydF4y2Ba（gydF4y2BaxgydF4y2Ba(第1节).因为我们储存gydF4y2BaPgydF4y2Ba（gydF4y2BaxgydF4y2Ba)在二次程序根处的计算(回忆gydF4y2Ba图2gydF4y2Ba)， worker必须首先插入来查找gydF4y2BaP (x)gydF4y2Ba然后进行多项式除法得到gydF4y2Bah (x)gydF4y2Ba．gydF4y2Ba

注意，所有这些计算都发生在一个正常的字段中，而worker的所有其他步骤都涉及到加密操作，其成本大约高出三个数量级。gydF4y2Ba

因此，人们可能naïvely得出结论，正如我们所做的，简单的多项式算法，如拉格朗日插值和“高中”多项式乘法，就足够了。然而，我们很快发现gydF4y2BaOgydF4y2Ba（gydF4y2BangydF4y2Ba^2gydF4y2Ba)的行为，在可验证计算所需的规模上，使线性数量的密码操作相形见绌(第5节)。因此，我们实现了基于fft的gydF4y2BaOgydF4y2Ba（gydF4y2BangydF4y2Ba日志gydF4y2BangydF4y2Ba)多项式乘法库，并使用多项式插值算法构建多项式二叉树，给出总时间gydF4y2BaOgydF4y2Ba（gydF4y2BangydF4y2Ba日志gydF4y2Ba^2gydF4y2BangydF4y2Ba)．即使如此优化，求解gydF4y2BahgydF4y2Ba（gydF4y2BaxgydF4y2Ba)是工人开销的第二大来源。gydF4y2Ba

为未来做准备;从过去吸取教训。gydF4y2Ba在我们的实现和评估中，我们假设了最坏的情况:客户端在没有任何警告的情况下决定将一个新功能外包出去，类似地，工作者只为给定的客户端计算单个实例。实际上，这两种情况都不可信。当客户机第一次安装Pinocchio时，程序可以构建前面讨论的单基数指数表。此外，它可以选择一个随机的s，并在后台开始计算s的幂，因为这些是完全独立于计算的。给定客户机的密钥，worker可以进行类似的优化。gydF4y2Ba

4.3.应用程序gydF4y2Ba

Pinocchio运行几个应用程序;每个都可以用一些静态实例化gydF4y2Ba参数,gydF4y2Ba然后每个实例都可以动态执行gydF4y2Ba输入。gydF4y2Ba虽然可以对其中一些应用程序使用自定义验证检查(例如，矩阵乘法)，但我们将它们包含进来是为了说明它们在像Pinocchio这样的通用系统中的性能。gydF4y2Ba

固定的矩阵gydF4y2Ba增加一个gydF4y2BangydF4y2Ba×gydF4y2BangydF4y2Ba矩阵参数gydF4y2Ba米gydF4y2Ba由一个gydF4y2BangydF4y2Ba长度输入向量gydF4y2Ba一个gydF4y2Ba，并输出结果gydF4y2BangydF4y2Ba向量的长度gydF4y2BaM·gydF4y2Ba答:我们选择五个参数设置，范围从|gydF4y2Ba米gydF4y2Ba| = 200 × 200 to |gydF4y2Ba米gydF4y2Ba| = 1000 × 1000。gydF4y2Ba

两个矩阵gydF4y2Ba有参数n，作为输入2gydF4y2BangydF4y2BaxgydF4y2BangydF4y2Ba矩阵gydF4y2Ba米gydF4y2Ba_1gydF4y2Ba而且gydF4y2Ba米gydF4y2Ba_2gydF4y2Ba，并输出gydF4y2BangydF4y2Ba×gydF4y2BangydF4y2Ba矩阵gydF4y2Ba米gydF4y2Ba_1gydF4y2Ba·gydF4y2Ba米gydF4y2Ba_2gydF4y2Ba．矩阵运算被广泛使用，例如在协同过滤(|gydF4y2Ba米gydF4y2Ba| = 30 × 30 to |gydF4y2Ba米gydF4y2Ba| = 110 × 110)。gydF4y2Ba

MultiVar聚gydF4y2Ba评估一个gydF4y2BakgydF4y2Ba- variable,gydF4y2Ba米gydF4y2Ba-次多元多项式。(gydF4y2Ba米gydF4y2Ba+ 1)gydF4y2Ba^kgydF4y2Ba系数是参数gydF4y2BakgydF4y2Ba变量gydF4y2BaxgydF4y2Ba_1gydF4y2Ba，gydF4y2Ba…,gydF4y2BaxgydF4y2Ba_kgydF4y2Ba是输入，多项式的标量值是输出(gydF4y2BakgydF4y2Ba= 5,gydF4y2Ba米gydF4y2Ba= 6,16,807 coeff。来gydF4y2BakgydF4y2Ba= 5,gydF4y2Ba米gydF4y2Ba= 10;644170年多项式系数)。gydF4y2Ba

图像匹配gydF4y2Ba参数化为gydF4y2Ba我gydF4y2Ba_wgydF4y2Ba×gydF4y2Ba我gydF4y2Ba_hgydF4y2Ba矩形图像及参数gydF4y2BakgydF4y2Ba_wgydF4y2Ba，gydF4y2BakgydF4y2Ba_hgydF4y2Ba．它接受输入agydF4y2BakgydF4y2Ba_wgydF4y2Ba×gydF4y2BakgydF4y2Ba_hgydF4y2Ba，并输出最小差值与点(gydF4y2BaxgydF4y2Ba，gydF4y2BaygydF4y2Ba)出现在图像中(gydF4y2Ba我gydF4y2Ba_wgydF4y2Ba×gydF4y2Ba我gydF4y2Ba_hgydF4y2Ba= 25,gydF4y2BakgydF4y2Ba_wgydF4y2Ba×gydF4y2BakgydF4y2Ba_hgydF4y2Ba= 9到gydF4y2Ba我gydF4y2Ba_wgydF4y2Ba×gydF4y2Ba我gydF4y2Ba_hgydF4y2Ba= 2025,gydF4y2BakgydF4y2Ba_wgydF4y2Ba×gydF4y2BakgydF4y2Ba_hgydF4y2Ba= 9)。gydF4y2Ba

最短路径gydF4y2Ba实施弗洛伊德-沃肖尔法案gydF4y2BaOgydF4y2Ba（gydF4y2BangydF4y2Ba^3.gydF4y2Ba)图算法，用于网络路由和矩阵反演。它的参数gydF4y2BangydF4y2Ba指定顶点的数量，它的输入是gydF4y2BangydF4y2Ba×gydF4y2BangydF4y2Ba边矩阵，它的输出是gydF4y2BangydF4y2Ba×gydF4y2BangydF4y2Ba全对最短路径矩阵(gydF4y2BangydF4y2Ba= 8,gydF4y2BaegydF4y2Ba= 64到gydF4y2BangydF4y2Ba= 24gydF4y2BaegydF4y2Ba= 576)。gydF4y2Ba

LGCAgydF4y2Ba是一个收敛于Navier-Stokes的晶格气体元胞自动机实现。它有参数gydF4y2BangydF4y2Ba为流体晶格大小，k为迭代次数。它输入1gydF4y2BangydF4y2Ba-单元格，并输出另一个反射gydF4y2BakgydF4y2Ba步骤(gydF4y2BangydF4y2Ba= 294,gydF4y2BakgydF4y2Ba= 5到gydF4y2BangydF4y2Ba= 294,gydF4y2BakgydF4y2Ba= 40)。gydF4y2Ba

sha - 1gydF4y2Ba没有参数。它的输入是13个字(416位)的输入字符串，并输出5个字(160位)的SHA-1散列。gydF4y2Ba

回到顶部gydF4y2Ba

5.评价gydF4y2Ba

我们在一台联想X201 ThinkPad上进行实验。我们运行在2.67 GHz英特尔酷睿i7的单核上，内存为8gb。gydF4y2Ba

下面，我们将重点比较之前的工作和应用程序级别的性能。在整篇论文中，我们提出了微基准来量化我们协议的基本成本单位。我们的结果表明，第4.2.1节中描述的优化在多项式操作中降低了23个数量级的成本，在幂运算中降低了310个因数。在宏观层面上，相对于原始的GGPR协议，gydF4y2Ba注册机gydF4y2Ba和Compute的速度是前者的两倍多，甚至验证速度也提高了24%。Pinocchio还大幅减少了评估键的大小，甚至设法将GGPR已经很苗条的9个元素证明的大小减少到8个元素。gydF4y2Ba

5.1.与相关工作比较gydF4y2Ba

图4gydF4y2Ba将匹诺曹的表现与相关系统的表现进行对比。我们使用两个矩阵的乘法作为我们的测试应用程序，因为它已经在之前的几篇论文中出现过，尽管存在更简单的、非加密的验证过程。由于所有这些先前的方案都是指定验证器，因此我们针对Pinocchio的指定验证器模式进行度量。gydF4y2Ba

我们将与(1)基于pcp的方案的naïve版本进行比较gydF4y2Ba^22gydF4y2Ba；(2) GGP,gydF4y2Ba^9gydF4y2Ba一个早期的方案定义了VC，但依赖于FHE;(3)胡椒,gydF4y2Ba^22gydF4y2Ba(1)的优化细化;(4)姜、gydF4y2Ba^23gydF4y2Ba胡椒的进一步改良;(5)拥有100万个并发实例的Ginger(见下文);(6)塞勒的后续系统，gydF4y2Ba^25gydF4y2Ba专门为基于交互协议的矩阵乘法和扩展工作量身定制。gydF4y2Ba^{7gydF4y2Ba，gydF4y2Ba12gydF4y2Ba}有关这些方案和它们之间的权衡的更多细节，请参阅第6节。由于这些方案大多不切实际得可笑，所以我们对它们的性能进行建模，而不是测量。对于GGP，我们基于FHE最近的性能结果建立了它的性能模型;对于塞勒，我们从报告的结果中推断gydF4y2Ba^25gydF4y2Ba；而对于其他的，我们使用了之前发布的模型。gydF4y2Ba^{22gydF4y2Ba，gydF4y2Ba23gydF4y2Ba}然而，对于匹诺曹，我们使用实现中的实数。gydF4y2Ba

图4gydF4y2Ba显示了匹诺曹延续了近期成本下降数量级的趋势。一个幼稚的基于pcp的方案需要数万亿年的时间来产生或验证一个证据。基于fhe的GGP协议显著提高了这一性能，但仍然不切实际。Pepper和Ginger在之前的工作基础上做了巨大的改进，但是，正如我们在第6节中更详细地讨论的那样，它们没有提供公开验证或零知识。gydF4y2Ba

除了提供新的属性外，Pinocchio还显著提高了性能和安全性。除了塞勒的工作，所示的系统gydF4y2Ba图4gydF4y2Ba跨多个工作实例摊销设置工作，gydF4y2Ba^cgydF4y2Ba但摊销的特点不同。为了达到收支平衡点，即客户机执行的验证工作少于本地执行的工作，Pepper和Ginger必须批处理工作实例，而GGP和Pinocchio必须执行足够多的实例来摊平关键设置成本。这些方法对延迟的影响非常不同。客户端不能从Pepper或Ginger中受益，除非它已经积累了一整批实例。在Pinocchio中，密钥设置可以预先计算，因此每个实例(包括第一个实例)都享有优于收支平衡的延迟。gydF4y2Ba图4gydF4y2Ba显示每个系统可实现的最小延迟。与单实例的Ginger相比，Pinocchio的验证器要快~120,000×17,000,000×， worker要快19×60×。为了提高性能，Ginger的参数的选择使得对手成功欺骗的概率可以高达gydF4y2Ba， (gydF4y2Ba图2gydF4y2Ba在裁判。gydF4y2Ba^23gydF4y2Ba)，而在《匹诺曹》中，概率是大致的gydF4y2Ba．gydF4y2Ba

最后，皮诺奇的验证比塞勒的自定义协议更有效，但塞勒的协议是唯一实现工作者实用性的协议，显示了其他系统为通用性所付出的代价。gydF4y2Ba

5.2.端到端应用程序性能gydF4y2Ba

我们在4.3节中描述的应用程序和参数设置中测量了Pinocchio的性能。所有应用程序都是用C编写的，并编译为qap和本机可执行程序。我们使用32位输入值来度量性能，因此可以与原生C版本进行比较。这显然使事情更具挑战性gydF4y2Ba

因为Pinocchio使用多精度整数在254位域上操作，而本地执行使用CPU的本机32位操作。gydF4y2Ba

图5gydF4y2Ba绘制Pinocchio的验证时间与本机执行相同应用程序的时间;每条线代表一个参数化的应用程序，每个点代表一个特定的参数设置。我们的关键发现是，对于足够大的参数，有三款应用跨越了外包的界限;也就是说，验证外包计算的结果比本地本地执行要便宜。注意，每个应用程序的直线的斜率是由我们实验的应用程序参数的大小决定的(例如，固定矩阵的参数比两个矩阵的参数更大)。gydF4y2Ba

另一方面，其他三款应用虽然发展方向正确，但都未能突破外包门槛。不同的是，这三个应用程序执行大量的不等式比较和/或位操作。这使得我们基于电路的表示相对于本地的效率更低，因此在我们当前的实验平台上，我们不能将应用程序参数设置推到它们可以击败本地执行的程度。尽管如此，这些应用程序在需要Pinocchio的零知识证明的设置中可能仍然有用。gydF4y2Ba

幸运的是，其他的实验表明，启用零知识证明增加了一个可以忽略的固定成本，密钥生成(213秒)，并且重新随机化一个证明使其为零知识需要很少的努力(例如，300毫秒或0.1%的多元多项式应用程序)。gydF4y2Ba

图6gydF4y2Ba提供了更多关于匹诺曹表演的细节。对于KeyGen，我们的实验保守地假设客户端在预期外包一个功能时不进行预计算，而对于Compute，我们假设工作者在丢弃其所有状态之前只执行一个工作实例。正如4.2.1节所讨论的，在实践中，我们将利用预计算和缓存之前的工作，这平均为KeyGen节省了至少43%的工作，为Compute节省了16%的工作。gydF4y2Ba

在gydF4y2Ba图6gydF4y2Ba，我们再次看到三个应用程序(星号)击败了本地执行，包括一个在公共验证器设置(每个IO需要更昂贵的操作)。数据还强调了一点，即使用电路表示在图像匹配、最短路径和相对于本机的晶格气体模拟上施加了显著的成本，建议进行优化。相对于电路表示，匹诺曹的验证是廉价的:与电路执行相比，公共验证者和指定验证者在大多数情况下都“赢”了。具体来说，指定的验证者在13个应用程序设置中的12个(92%)中获胜。公共验证更昂贵，特别是对于大型IO，但仍然在13个设置中的9个(69%)获胜。gydF4y2Ba

由于Pinocchio提供公开验证，一些客户将从其他人的KeyGen工作中受益，因此只关心验证成本。例如，手机运营商可能会执行一次性的KeyGen，以便其客户可以验证任意工人所做的计算。gydF4y2Ba

然而，在其他设置中，例如，一个公司将工作外包给云，密钥生成器和验证者可能是同一个实体，并且希望通过验证节省的成本来摊销密钥生成的成本。gydF4y2Ba图6gydF4y2Ba这表明大多数应用与电路执行相比都有一个较低的“收支平衡”点:指定验证器的中位数是555个实例，公共验证器的中位数是500个实例。之后的每一个实例都是一次“胜利”，甚至对于密钥生成器来说也是如此。gydF4y2Ba

图6gydF4y2Ba对匹诺曹来说还有更多的好消息:它生成的键大小合理，评估键(描述整个计算)通常需要10秒或100 MB。弱验证器的键(随着I/O线性增长)通常只有几KB，即使在其最大的情况下，对于双矩阵乘法，它只需要略多于1 MB。这表明键是非常便携的，不需要过多的带宽来传输。gydF4y2Ba

最后，从客户机的角度来看，如果工作者的努力是免费的，那么工作者生成证明的额外开销就无关紧要了，只要它不影响响应延迟。我们的结果，结合之前在并行化方面的工作，gydF4y2Ba^23gydF4y2Ba建议将延迟降低到合理的水平。事实上，在高保证的场景中，在客户端无法执行计算本身的场景中(例如，一个电力有限的设备)，或者在worker的资源是空闲的场景中，客户端很可能将worker视为“空闲的”。gydF4y2Ba

然而，在其他场景中，比如云计算，工作人员的努力不是免费的。即使在这里，陈和锡安gydF4y2Ba^6gydF4y2Ba估计对于一个小型企业来说，云计算的成本大约是本地计算的60倍。这为我们应该愿意增加到工人开销中的额外工作量提供了一个大致的上限。gydF4y2Ba

回到顶部gydF4y2Ba

6.相关工作gydF4y2Ba

在实现验证计算时，先前的工作集中于交互式证明或pcp。一个努力gydF4y2Ba^{7gydF4y2Ba，gydF4y2Ba25gydF4y2Ba}建立在Goldwasser等人的交互式证明的基础上。gydF4y2Ba^12gydF4y2Ba(GKR)。它们的目标是一个流设置，客户端不能存储它想要计算的所有数据;该系统目前要求计算的函数具有高度并行性。从好的方面来说，它不需要密码学，而且它对计算上不受限制的对手是安全的。gydF4y2Ba

Setty等人生产了一系列基于pc的系统，称为PeppergydF4y2Ba^22gydF4y2Ba和姜。gydF4y2Ba^23gydF4y2Ba它们建立在一种叫做线性PCP的特殊类型的PCP上，gydF4y2Ba^14gydF4y2Ba证明可以用线性函数表示。这允许工作人员使用线性同态加密方案来创建对其证明的承诺，而只依赖于标准的加密假设。通过理论和系统相结合的改进，使基于pcp的系统在实用化方面取得了巨大进展。实际上，对于能够容忍大批处理的应用程序，验证的平摊成本可以相当低。gydF4y2Ba

然而，仍有一些缺点。因为这项研究建立在阿达玛PCP的基础上，gydF4y2Ba^1gydF4y2Ba除非协议是手工定制的，否则设置时间、网络开销和证明者的工作是原始计算规模的二次元。为了提高效率，验证器在完整的批返回之前不能验证结果。该方案是指定的验证者，这意味着第三方无法验证外包计算的结果，除非共享客户端的秘密密钥并冒欺诈的风险。该方案也不支持零知识证明。gydF4y2Ba

并发工作gydF4y2Ba^21gydF4y2Ba也建立在Gennaro等人的二次程序的基础上。gydF4y2Ba^10gydF4y2Ba他们观察到qap可以被视为线性pcp，因此可以适合Ginger的密码框架。gydF4y2Ba^23gydF4y2Ba他们的研究显示，工人的计算能力得到了类似于匹诺曹的提高。它们保留了pcp和Ginger的密码协议，因此它们依赖于比Pinocchio更简单的密码假设，但它们仍然必须进行批处理计算才能获得有效的验证器。它们仍然是指定的验证者，不支持零知识证明。gydF4y2Ba

后续工作gydF4y2Ba^3.gydF4y2Ba通过将Pinocchio的加密协议与RAM访问的创新编码相结合，扩展了应用程序的表达能力。他们还提出了一种基于通用CPU的优雅程序编码，但对于矩阵乘法等应用程序来说，这导致了与Pinocchio相比57个数量级的开销。gydF4y2Ba

有几个系统为零知识(ZK)证明提供编译器。gydF4y2Ba^17gydF4y2Ba一般来说，这些系统在其特定的功能子集方面可能表现出比Pinocchio更好的性能，但它们没有相同级别的高效通用性。gydF4y2Ba

回到顶部gydF4y2Ba

7.结论gydF4y2Ba

我们展示了一个名为“匹诺曹”的公共可验证计算系统。匹诺曹使用了一种新的编码计算方法二次程序，结合一种高效的加密协议，实现了渐近和具体效率。不管计算的大小如何，Pinocchio都会生成288字节的证明，而且证明可以快速验证，通常只需几十毫秒，在某些情况下胜过本机执行。这代表五到七gydF4y2Ba数量级gydF4y2Ba在之前工作的基础上改进性能。gydF4y2Ba^23gydF4y2Ba工人也生产证明19×60×更快。匹诺曹甚至大幅削减了底层协议的成本，将密钥和证明生成的成本降低了60%以上。最终的结果是一个有效签名计算的加密协议。与真正C程序的编译器相结合，Pinocchio使VC更接近于实用性。gydF4y2Ba

回到顶部gydF4y2Ba

回到顶部gydF4y2Ba

回到顶部gydF4y2Ba

回到顶部gydF4y2Ba

回到顶部gydF4y2Ba

数字图书馆是由计算机协会出版的。版权所有©2016 ACM, Inc.gydF4y2Ba

---

没有找到条目gydF4y2Ba