0x00 Abstract
继 Gennaro、Gentry 和 Parno（Cryptology ePrint Archive 2009/547)之后，我们使用完全同态加密来设计委托计算的改进方案。在此方案中，委托人将函数 F 输入在许多动态选择中 xi 上述计算外包给员工，使员工无法让客户接受 F (xi) 以外的结果。 Gennaro 等人的在线阶段。方案非常有效：双方交换两条信息，客户及时 poly(log T ) 工作人员及时运行 poly(T ) 中间运行，其中 T 是 F 时间复杂。然而，离线阶段(取决于函数 F 而不是委托输入）效率低下：客户及时运行 poly(T ) 生成需要访问的长度 poly(T ) 工人在线阶段使用公钥。
我们的第一个结构被消除了 Gennaro 等人的大公钥。方案。客户在离线阶段仍在投资 poly(T ) 但不需要沟通或发布任何内容。我们的第二个结构将客户在离线阶段的工作减少到 poly(log T)，代价是与 poly(T)-time worker 进行 4 条消息(离线)互动(无需与) worker 在线阶段使用相同)。最后，我们描述了实现第二个结构的装配线，避免了检测到错误后重新运行离线结构的需要（假设错误不太频繁）。
关键词：可验证计算、外包计算、最坏情况/平均情况减少、合理证明计算、一般论证系统。
0x01 Introduction
委托计算的问题考虑了这样一种情况，即委托方希望将函数计算出来 f 的计算委托给另一方党, 工人.挑战是客户可能不信任员工，所以希望员工的证明计算正确完成。显然，我们希望验证这个证书比计算更容易。
这种外包计算的概念与现实世界中的几个场景有关，如下面三个示例所示(取自 [GGP09,GKR08]）：
- 志愿计算。志愿者计算的想法是让服务器将大计算分为小单元，发送给志愿者，然后重新组合结果（通过更简单的计算）。开放基础设施计算伯克利网络 (BOINC) [And03,And04] 就是这个平台的例子。使用 BOINC 平台上的一些著名项目是 SETI@home 和 Great Internet Mersenne Prime Search [Mer07]。建议读者参考 [GKR08] 了解更多关于这些项目的细节。
- 云计算。在云计算的背景下，企业从服务中购买计算时间，而不是自己的计算资源。
- 弱移动设备。移动设备，如手机、安全访问卡、音乐播放器和传感器，算上通常非常薄弱，因此需要远程计算机的帮助来运行昂贵的计算。
关于这种情况，一个很自然的问题是:工人不诚实怎么办？例如，在志愿者计算设置中，敌对志愿者可能会将错误引入计算。在云计算示例中，云（即提供计算服务的业务）可能会有经济动机来返回错误的答案。如果这个答案需要更少的工作，并且不太可能被客户机检测到。此外，在某些情况下，外包给云的应用程序可能非常关键，客户希望消除计算过程中的意外错误。对于弱移动设备，设备与远程计算机之间的通信通道可能会被对手破坏。
在实践中，许多项目通过冗余来处理这种欺诈；同一个工作单位被发送给几名工作人员，然后比较结果的一致性。然而，这需要使用几名工人来防止工人串通。
相反，我们希望工人正确计算委托证书。当然，验证所需的时间明显小于实际操作所需的时间。同时，证明工作人员的运行时间也应合理——相当于计算所需的时间。例如，当委托计算一个耗时T、输入和输出长度为n的函数f时，我们希望委托运行时间为poly(n, log T)，工作函数运行时间为poly(T)。
1.1以前的工作
从[Bab85,GMR从89开始，概率证明系统的大量工作与安全委托密切相关。事实上，在输入x计算委托函数f并发送结果y后，worker可以使用各种类型的证明系统来说服客户相信f(x) = y这个陈述。
互动的证明。IP=PSPACE定理[LFKN92,Sha92]对于任何可在多项空间中计算的函数f，验证器(委托)运行时间为多项时间。但证明者(工作者)的复杂性仅限于多项空间(因此是指数时间)。这个定理是精制和按比例缩小(FL93)给验证器复杂性聚(n, s)和验证的复杂性2聚为函数f (s)输入长度可在时间T和空间年代计算n。注意，验证的复杂性仍然存在superpolynomial T,即使是在尽可能小的空间内运行的计算s = O (log T)。然而，最近Goldwasser等人[GKR将证明的复杂性改进为poly(T, 2s)，即poly(T) we n s = O(log T)。更一般地，Goldwasser等人[GKR给出了小深度d(即并行时间)计算的交互证明。对于这些，它们实现了证明复杂性poly(T)并验证复杂性poly(n, d, log T)。(这意味着空间有界计算的结果，因为运行在时间T和空间s中的算法可以转换为时间poly(T, 2s)和深度d = O(s2)运行算法中的算法。)但是，如果不局限于小空间或小深度的计算，就不能使用交互证明。事实上，任何与验证人的运行时间（通信）TV交互证明的语言可以在空间中poly(n, TV)中确定。
pcp和MIPs。MIP=NEXP定理[BFL91]和Babai等人[BFLS91]给出了时间T计算的多证交互证明和概率检验证明，证明运行在时间poly(T)及时验证操作poly(n, log T)，完全符合我们的要求。然而，使用这些委托需要特殊的通信模型——要么是两个非通信验证人，要么是验证人随机访问验证人PCP(长度为poly(T))验证人在验证期间不能更改机制PCP。
互动参数。交互论证[BCC88](合理证明也称计算)[Mic94]将合理性条件放宽为计算，而不是改变通信模型。也就是说，不是要求任何证明策略都不能说服错误陈述的验证者，而是要求任何计算可行的证明策略都不能说服错误陈述的验证者。在这个模型中，Kilian [Kil92]和Micali [Mic94]证明复杂性poly(T, k)并验证复杂性poly(n, k, log T)的恒轮协议(其中k为安全参数)，并假设存在抗碰撞函数。在亚指数硬度假设下，安全参数可以从小到小polylog(T);下面描述的方案也是如此。
交互解决方案。在这项工作中，我们对接近非交互解决方案感兴趣（具有计算可靠性）。理想情况下，工人/验证人应能够在发送计算结果的同一信息时向委托/验证人发送证书。
这种可能性的有效非交互参数是由Micali [Mic94]，验证表明非交互参数复杂性保利(T, k)复杂性聚和验证器(n, k,日志T)可以随机预测模型(Oracle用于消除交互la菲亚特-沙米尔[FS86])。试探性地，人们可能希望使用适当的哈希函数族实例化oracle，我们可以获得委托计算的非交互式解决方案：在离线阶段，验证人/委托人（或可信的第三方）从家庭中选择并发布随机哈希函数，而在线阶段，证明完全非交互（从验证人到验证人只有一条信息）。然而，众所周知，随机性Oracle一般来说，启发式是不可靠的[CGH04]，甚至在Fiat-Shamir [Bar01,GK在03的背景下也是如此。因此，有效的非交互参数的存在，尽管付出了很多努力，在复杂性和密码学上仍然是一个重要的开放问题。
最近在减少互动方面取得了一些进展。通过Kalai和Raz [KR09]的转换，Goldwasser、Kalai和Rothblum [GKR08]显示了如何将小深度计算的交互证明转换为公钥模型中的非交互参数（假设有单个服务器的私人信息检索）(PIR)方案):在脱机阶段，验证人/委派人生成公钥/秘钥对，发布公钥并存储秘钥。然后，在线阶段，验证人/工作人员检索公钥，并构建证书并与计算结果一起发送。然而，与[GKR08]的交互证明一样，这个解决方案只适用于小深度的计算，因为验证者的复杂性随深度线性增长。
最近，Gennaro、Gentry和Parno [GGP09]显示了如何通过增加验证器的离线复杂性和公钥尺寸，以及使用完全同态加密(FHE)方案(最近由Gentry [Gen构建)任意计算。委托在他们的建筑物投资保利(T, k)离线阶段构建公钥的大小保利(T, k)与密钥大小聚合(k) (f o r d e l e g T i n g f u n c T i o n f可计算的时间T)。在线阶段，委托运行时间减少了聚集(n, k,日志T)保利是长n的输入，工人的复杂性(T, k)。因此,在委托的大型投资在离线阶段可以平摊在网上的许多执行阶段委托f的计算资源。他们的在线舞台并非完全没有互动，而是由两个信息组成。然而，在许多应用程序中，由于委托可能需要将输入x传递给工作人员，无论如何都有必要提供两条信息。
我们注意到，在客户拥有密钥的方案中(即[GKR08]和[GGP09]，以及我们以下两个结构），只有当对抗员工不知道授权人拒绝证明时，才能保证其稳定性。因此，接受/拒绝的决定应保密，或在拒绝后重新运行（可能非常昂贵）。
1.2我们的结果
在这项工作中，我们提供了以下协议，以改进Gennaro等人的工作[GGP09]:
- 我们的第一个协议消除了Gennaro等人方案的大公钥。也就是说，委托在脱机阶段仍然执行poly(T, k)工作，但这次计算的结果只是一个长度为poly(n, k, log T)的秘钥;在在线阶段之前，不需要与工作者进行任何交互(甚至不需要传输公钥)。
- 我们的第二个协议将离线阶段的委托工作减少到poly(n, k, log T)，代价是与时间为poly(T, k)的worker进行恒轮交互。在这个协议中，在一个被拒绝的证明之后重新运行离线阶段变得更加合理。因此，没有理由对接受/拒绝的决定保密。
- 最后，我们描述了第二个协议的“流水线”实现，它避免了重新运行脱机阶段的延迟，同时保持了可靠性，即使接受/拒绝的决定被揭示。此解决方案要求双方都维护状态，并且如果故障不经常发生，则保持完整性。因此，这个解决方案最适用于这样的情况:委托多次使用一个worker，并且有随机错误(在通信或计算)可能导致委托偶尔拒绝。
与[GGP09]一样，我们所有的协议都要求使用完全同态加密方案，并有一个2消息在线阶段。表1给出了我们的模型和结果与以往工作的完整比较。
组织。关于完全同态加密方案的初步介绍见第2节。然后我们在第3节给出我们的模型的正式定义。在第4 - 8节中，我们从一个简单的方案Del1开始，它实现了相当弱的属性，并通过一系列步骤加强它，从而得到我们的主要委托方案Del4和Del5。
由于空间限制，我们跳过了所有的证明。详细内容请参考本文全文[CKV10]。
0x02 关于完全同态加密的初步研究
受Gennaro, Gentry和Parno [GGP09]最近关于安全授权的工作的启发，我们的结构依赖于使用完全同态加密方案。
完全同态加密。如果一个公钥加密方案 E = (KeyGen, Enc, Dec) 与一个额外的多项式时间算法 Eval 相关联，则称它是完全同态的，该算法将公钥 pk 作为输入，密文 ^x = E n c ( x) 和电路 C，并输出一个新的密文 c = Evalpk(^x, C)，使得 Decsk(c) = C(x)，其中 sk 是与公钥 pk 对应的密钥。要求 c = E v a lpk(Encpk(x), C) 的大小在多项式上取决于安全参数和 C(x) 的长度，但在其他方面与电路 C 的大小无关。我们还要求Eval 是确定性的，并且该方案具有完美的正确性（即它始终保持 Decsk(Encpk(x)) = x 和 Decsk(Evalpk(Encpk(x), C)) = C(x)）。为了安全，我们只要求 E 在语义上是安全的。
在最近的一项突破中，Gentry [Gen09] 提出了一种基于理想格的完全同态加密方案。在他的基本方案中，算法的复杂性（KeyGen、Enc、Dec）线性依赖于电路 C 的深度，其中 d 是电路 C 深度的上限，允许作为 Eval 的输入。然而，在他的方案是循环安全的附加假设下（即，即使给定密钥的加密，它仍然是安全的），这些算法的复杂性与 C 无关。此外，Gentry 的构造满足完美的正确性和 Eval他的方案可以是确定性的。详情请参阅 [Gen09]。
[GGP09] 构造的一个有趣方面是他们如何使用完全同态加密方案的保密属性来实现其委托方案中的健全性；这种现象在我们的工作中也多次出现。
0x03 模型
在本节中，我们正式定义了一个模型来捕获我们感兴趣的委托计算场景。
定义 1（委派方案）。委托方案是一个交互协议 Del = ?D, W?委托人 D 和工作人员 W 之间的结构如下：
......