一种最优分布式离散日志协议及其 在同态秘密共享中的应用外文翻译资料

本科毕业设计（论文）

文献翻译

一种最优分布式离散日志协议及其

在同态秘密共享中的应用

作者：Itai Dinur, Nathan Keller, and Ohad Klein

国籍：以色列本古里安大学计算机科学系

出处：以色列巴伊兰大学数学系

摘 要：本文介绍了Boyle等人提出的分布式离散对数(DDL)问题.2016年。解决这一问题的协议是其同态秘密共享(HSS)方案的共享转换过程中使用的主要工具，它允许双方通过秘密输入的共享对分支程序进行非交互式评估。

设g是乘法群G的生成元。给定随机群元素和未知整数对一个小M，如果，则A和B(不能通信)成功地求解DDL。否则，当事人就会犯错。在Boyle等人的DDL协议中，A和B在T时间内运行，在M=T中具有大致线性的错误概率。由于它对HSS方案的性能没有影响，这是Boyle等人提出的一个主要的开放性问题。是将错误概率降低为T的函数。在本文中，我们设计了一种新的DDL协议，该协议将错误概率大大降低到。我们的新协议改进了Boyle等人提出的HSS方案的渐近评估时间复杂度。关于大小为S的分支程序从到。我们进一步证明了我们的协议是最优的，直到所有相关的密码群族的常数因子，除非一个人能够解决离散对数p问题在较短的长度R的时间间隔。我们的DDL协议是基于一种新的随机游动，它由多个迭代构成，期望步长逐渐增加。我们相信，这种随机游走是独立的兴趣，并将有更多的应用。

关键词：同态秘密共享，共享转换，完全同态加密，离散对数，短间隔离散对数，随机游走。

1. 介绍

同态秘密共享

同态秘密共享(HSS)是实现完全同态加密(Fhe)[13，19]的一种实用方法。提供了它的一些功能。2016年由Boyle、Gilboa和Ishai[5]介绍，并在[4，6，7，11]中作了进一步的研究和扩展。与传统的安全多方计算协议[1，8，22]相比，HSS的主要优点是，与FHE类似，它的通信复杂度小于计算函数的电路大小。

HSS允许在不交互的双方之间分配同态评估。一种(2方)hss方案将输入w随机分成一对共享，使得：(1)每个共享在计算上隐藏w，(2)存在一个多项式时间局部评估算法Eval，使得对于来自给定类的任何程序P(例如布尔电路或分支程序)，输出可以从Eval和Eval中重建。

[5]的主要结果是在Diffie-Hellman假设下，满足=Eval和Eval的分支程序的HSS方案。后来在[4，6]中进行了优化，其中优化的变体的安全性依赖于其他离散日志样式的假设。

设G是素数阶N的乘性循环群，其中离散对数问题可能是硬的，且g是这个群的生成元。[5]方案允许各方用附加秘密共享(小)值在本地乘加密(小)输入，从而使结果在各方之间共享。问题是，在这个阶段，是由各方以乘法方式共享的，因此它们不能用新的加密输入乘以z。也许[5]中最具创新性的想法允许各方通过股份转换程序将的乘数份额转化为z的可加性股份，而无需任何相互作用。一旦双方拥有z的加性共享，他们就可以继续将其添加到其他可加性股份中。这些操作允许评估限制乘法直线(RMS)程序，该程序可以使用O(S)指令模拟任何大小为S的分支程序。

[5]的股份转换程序在当事人可能犯错的意义上是不完善的。更具体的fi是，各方不能用依赖于各方运行时间T的错误概率delta;和以中间计算值为界的小整数M来计算z的正确加性份额。由于在EVAL执行过程中执行了多次的股票转换，其总错误概率累积并大致变为，其中S是RMS程序执行的乘法次数。因此，如果总错误概率为常数，则必须在股票转换过程中设置各方的运行时间T，从而使.错误交易的运行时间对HSS方案的性能有很大的影响。

由于HSS背后的主要动机是为FHE提供一种实用的替代方案，因此[5]中提出的主要开放问题之一是提高股票转换过程中错误交易的运行时间。在后续工作[4，6]中，这一开放问题取得了进展，这表明能够很好地提高HSS方案的实用性。尽管取得了这一进展，但股票转换过程的误差交易的渐近运行时间并没有明显改善，所有方案的运行时间T与反向错误概率(或一般为)线性增长(大致)。因此，要获得，必须设置，并且由于P中的乘法总数为S，所以总运行时间为。

分布式离散日志问题(DistributedDiscreteLogs，DDL)

本文研究的重点是各方在股票转换过程中共同解决的分布式离散日志(DDL)问题。为了简单起见，我们现在描述DDL问题并抽象出HSS的细节。DDL问题涉及A和B两方。A的输入由一个群元素组成，其中x是从随机一致选择的。B的输入由组成，其中bisin;[minus;M，M]是区间内未知的一致选择整数(对于一个小的带轴整数参数M)。算法A，B受参数T的限制，该参数限制了允许它们计算的组操作的数目。^[1]在执行算法后，每一方输出一个整数。如果，则各方成功地解决了DDL实例。我们强调，不允许A和B进行交流。^[2]

如果由A(第0方)和B(第1方)乘数共享，则。在股份转换过程中，甲方运行，乙方运行。假设它们正确地解出了的DDL，则，即和是z的加性份额。

将DDL问题看作一个同步问题是很方便的：A和B试图从输入的指数中同意或同步具有已知off集的组元素。如果他们设法这样做，各方通过输出这个off集来解决DDL问题。例如，如果双方在上同步，则而，因此。特别是，如果A和B都能解决其输入的离散对数问题(即分别计算和)，则可以通过输出和在生成器g上同步。当然，这将违反HSS方案的安全性，这意味着G中的离散对数问题应该是困难的，而A、B必须通过其他方法才能成功。

我们的目标

本文的目标是为A和B(即DDL协议)设计算法，使它们的成功概率最大化(接管x，b的随机性)，或等效地，我们的参考点是[6]的DDL协议(它是原delta;协议[5]的版本)，它实现了参数T和错误概率delta;之间的线性交易。更准确地说，在A，B是允许T群操作的情况下，DDL错误概率大致是M/T。事实上，在[4-6]中设计的几种密切相关的协议在参数T和错误概率之间给出了类似的线性交易delta;。

本文的另一个目的是更好地理解DDL协议的局限性。更具体的，我们的目的是证明下界的错误概率的DDL协议，减少了一个已得到充分研究的计算问题对DDL组的DDL。特别地，我们对区间问题(DLI)中的离散日志很感兴趣，其中输入由一个已知长度R的区间中的组元素组成，目标是计算它的离散日志。

DLI一直是密码分析领域深入研究的对象，其中最著名的算法是经典的步长级巨步算法和Pollard[17]的记忆全知变体(额外的扩展见[12，18])。这些算法以碰撞finding为基础，其复杂度约为，它们在具体的素阶群族(其中离散对数很难)中最为著名，特别是对于椭圆曲线群，其区间R的大值是最著名的。最著名的DLI算法的复杂度约为，其中R与群N的大小一样大(给出了标准的离散对数问题)。对于其他群(如的素数阶子群)，最著名的复杂性是关于，其中R可以在上达到次指数(因为离散对数在这些群中可以用次指数复杂度来求解[14，15])。我们注意到，DLI除了与密码分析相关外，还作为某些密码系统解密过程的一部分来求解(尤其是在Boneh、Goh和Nissim[3]的密码系统中)。

建立DDL错误概率下界的另一种方法是使用Shoup[20]提出的通用群模型(GGM)。在GGM中，不允许算法直接访问组元素的位表示，但只能获得元素的随机编码，这些编码可以通过oracle查询获得。一般群模型是一个标准模型，用于证明群上某些(可能是困难的)问题的计算下界，从而建立其硬度的fi值。虽然在GGM中得到的界与一类受限的算法有关，但它本质上是已知群上某些计算问题(如离散日志)有意义的下界的唯一模型。此外，对于一些问题(如某些椭圆曲线群中的离散对数计算)，一般算法本质上是已知的最佳算法。这种替代证明方法的缺点是它不直接将DDL与群族中的任何困难问题联系起来，而是在抽象模型中建立了一个下限证明。

我们的贡献

这项工作的主要结果是通过给出基于DLI在这些家族中的硬度的上、下界，来缩小DDL在许多具体群体中的差距。我们提出了一种改进的fi协议，该协议适用于任意G群，实现了参数T与错误概率之间的二次，即。这与[4-6]中得到的线性交易delta;=O(M/T)相比有很大的改进。因此，在具有乘法复杂度S的RMS程序P上执行Eval时，可以设置来获得，使总运行时间从[4-6]中的减少到O()。这一结果直接改进了[4-6]中给出的一些HSS应用程序的计算复杂度。例如，在私有信息检索[9](PIR)中，客户端私下搜索分布在多个服务器之间的数据库，以寻找满足谓词P的文档。[5]的1轮2服务器PIR方案支持一般搜索，表示为应用于每个文档的S分支程序。Boyle等人方案中每个文档的计算复杂度。是，我们的结果将这个复杂度降低到O()。

在实际应用方面，我们通过广泛的实验充分验证了我们的协议。我们进一步考虑了[4，6]中为DDL实现的优化，这些优化对DDL的具体运行时间没有影响。虽然将这些优化应用于我们的DDL协议并不简单，但我们将展示如何调整我们的协议，使其也能从这些优化中受益。总的来说，我们相信我们的新的DDL协议将使我们能够在最有效的HSS实现[4]上提高几个数量级，并使它对新的应用程序具有实用价值。

我们的DDL协议使用了一种由多个迭代组成的新型伪随机游动。每一次迭代都类似于Pollard的“袋鼠”随机游动算法，用于使用有限内存求解DLI[17]。但是，DDL是不同于DLI，因为各方无法进行通信并寻求最小化它们的错误概率(而不是使其常量)。这导致了一种更复杂的迭代算法，其中各方仔细地将它们的时间复杂度T分布在几个随机行走迭代中。这些迭代使用越来越长的步长，从而逐渐减少向)方向的错误概率。

新的随机游走使输入接近的各方在没有通信的情况下在公共输出上达成一致(或同步)的概率最大化。我们相信这种随机游动是独立的，它将使fi和其他应用超出同态秘密共享方案和密码学的范围。

在给出我们的DDL协议后，我们着重讨论了该协议的下界，并证明了对于一个群族，任何DDL协议都必须具有的错误概率，除非该族中的dll(具有长度R的间隔)可以在时间上求解。对于标准密码组中的小(多项式)T(基于组的hss方案被认为是安全的)，这是目前无法实现的。

最后，对通用组模型中的DDL协议进行了分析。在该模型中，我们的DDL协议是自适应的，因为A和B的Oracle查询取决于它们先前查询的答案。这与GGM中的[4-6]协议形成了对比，GGM中的甲骨文查询是预先进行(或从前一组大小为O(T))中高概率地选择的。因此，自然会问是否需要自适应来获得GGM中最优的DDL协议。有趣的是，我们证明了答案是肯定的。实际上，我们证明了[4-6]中得到的线性交易本质上是GGM中非自适应DDL协议的最佳选择。

1. 内容组织

论文的其余部分按以下方式组织。我们在第2节中描述了初步的内容，并在第3节中概述了我们的新协议和相关工作。第四节分析了新的DDL协议。我们在第5节中证明了具体群体族中DDL错误概率的下界，在第6节中证明了GGM中非自适应算法的下界。

1. 准备工作

在本节中，我们将描述这项工作所需的准备工作。本文首先介绍了本文中使用的符号，然后给出并分析了[5]中的DDL算法，作为算法的基础。为了完整起见，我们对附录A中[5]的基于群的同态秘密共享方案作了简要的描述。

2.1分布式离散日志问题的表示法

回想一下，如果，则双方A和B成功地解决了DDL实例。为了简化我们的表示法，我们通常不会显式地将参数G、g、N、M、T写在A，B的描述中，尽管其中一些参数会出现在分析中。我们感兴趣的是A和B的成功(或错误)概率，接管了x，b的随机性(也可能超过A，B的随机性)。我们用表示错误事件，并由表示其概率，其中和bisin;[M1，M2]是一致的(通常，我们感兴趣的是)。我们还用suc(A，B，x，b，T)表示互补成功事件。

当双方执行相同的算法A时，我们将该表示法分别缩短为，和suc(A，x，b，T)。如果从上下文中可以看出参数A、B、x、b、T，我们有时会使用err和suc代替err(A、B、x、b、T)和suc(A、B、x、b、T)。正如上面提到的，A和B可以是随机算法，在这种情况下，成功(和错误)的概率也被考虑到了它们的随机性上。然而，为了简化我们的表示法，我们通常不会显式地引用这种随机性。

我们注意到，[4-6]中考虑的

剩余内容已隐藏，支付完成后下载完整资料

英语原文共 47 页，剩余内容已隐藏，支付完成后下载完整资料

资料编号：[272204]，资料为PDF文档或Word文档，PDF文档可免费转换为Word