毕业论文外文文献翻译

安全计算协议

作者：Andrew C. Yao

出处：University of California Berkeley, California 94720

1 介绍

两位百万富翁想知道谁更富有，然而，他们不想无意中发现任何关于彼此财富的额外信息。他们怎么能进行这样的对话？

这是以下一般问题的特例。假设m个人希望计算函数f(x1，x2，x3，...，xm)的值，该函数是有界范围的m个整数变量xi的整数值函数。首先，人Pi知道xi的价值，而不知道其他x的价值。他们是否有可能通过相互之间的交流来计算f的值，而不会过度地泄露任何有关其自身变量值的信息？百万富翁的问题对应于当m = 2，f(x1，x2)= 1，如果x1 lt;x2，否则为0。在本文中，我们将给出这个一般问题的精确公式，并描述通过使用单向函数（即易于评估但难以反转的函数）解决它的三种方法。这些结果可用于秘密投票，私人查询数据库，不经意的谈判，玩精神扑克等。我们还将讨论复杂性问题“需要交换多少比特来进行计算”，并描述方法防止参与者作弊。最后，我们研究了“单向函数无法实现的问题”。

在描述这些结果之前，我们希望通过在下一章中首先考虑安全计算的统一视图来深入研究这项工作。

2安全计算的统一视角

由于单向函数最初是在1976年提出的(Diffie和Hellman [1])，它们已被用于两种应用中。 第一种是关于消息的加密和传输，使窃听者和破坏者不可读和不可改变[1,2,3,4]。 第二种应用包括“精神扑克”(Shamir，et.al。[5])，其中两个玩家通过电话线进行通信，以及“硬币翻转”(Blum [6])，其中两个 相互怀疑的各方都要产生一个无偏见的位。 期望有一个统一的框架，其中所有这些应用程序都可以相关，并且可以开发用于证明协议安全性的通用技术。 更重要的是，如果我们要了解单向函数的内在力量和局限性，这样的框架是必不可少的。例如，如果没有精确的模型，就很难回答诸如“三个相互怀疑的各方是否有可能以1 / e的偏差交互式产生一点？”这样的问题。

为了满足这一需求，我们建议采用以下观点。 分别拥有私有变量i和j的两方Alice和Bob希望进行通信，以便Alice可以评估函数f(i，j)，并且鲍勃函数g(i，j)。 通信线路上可能存在一些窃听者或破坏者。 协议的目的是设计一个算法，让Alice和Bob遵循，这样就可以满足某些安全约束（针对破坏者）和隐私约束（Alice可能不希望揭示i的确切值）。

在一个极端情况下，当计算组件是微不足道的时，例如， 如果f =常数且g(i，j)= i，那么我们得到之前提到的第一种应用，其中基本的关注点是窃听和破坏。 在另一个极端，当可以忽略这些外部威胁，但f和g的计算是不平凡的，那么我们就会得到本文要研究的问题。(精神扑克和硬币翻转代表了这个问题的随机版本，也将对此进行讨论。)请注意，虽然我们在上面的描述中使用了Alice和Bob，但所有讨论都可以扩展到m方通信的情况。

一起讨论这两个特殊情况是很自然的。 但是，由于长度考虑，我们将在此仅报告与计算密集的情况相对应的结果，没有外部破坏者。 其他案件的结果将在别处报告。

3确定性计算

3.1解决百万富翁问题

在这个摘要中，我们将仅详细描述我们拥有的三种解决方案中的一种。

确切地说，假设Alice拥有数百万美元而Bob拥有数百万美元，其中1 lt;i，j lt;10。我们需要一个协议来决定我是否ilt;j，这样这也是他们最终知道的唯一事情(除了他们自己的价值观)。 设M是所有N位非负整数的集合，Q_N是从M到M的所有1-1的集合。让E_a成为Alice的公钥，通过从Q_N中选择一个随机元素生成。

该协议如下：

1. Bob选择一个随机的N位整数，并私下计算E_a（x）的值; 调用结果k。

2. BobsendsAlicethenumberk-j 1;

3. Alice私下计算y_u = D_a（k-j u）for u=1,2，...，10。

4. Alice生成N / 2比特的随机素数p，并计算所有u的值z_u = y_u(mod p); 如果所有z_u在mod p意义上至少相差2，则停止; 否则产生另一个随机素数并重复该过程，直到所有zu相差至少2; 让p，z_u表示最后一组数字;

5.Alice将素数p和随后的10个数字发送到B：z₁，z₂，...，z_i，然后是z_i 1，z_{i 1} 1 ,hellip; ，z₁₀ 1; 上述数字应该在模式意义上解释。

6. Bob查看从Alice发送的第j个数字(不计算p)，并且如果它等于x mod p则判定ige;j，否则i lt;j。

Bob告诉Alice结论是什么。

该协议清楚地使Alice和Bob能够正确地决定谁是更富有的人。 为了表明它满足了他们无法获得关于另一方财富的更多信息的要求，我们需要定义一个精确的模型，该模型将在3.2节中完成。 在这里，我们将非正式地论证为什么要求得到满足。

首先，Alice不会对Bob的财富j一无所知，除了鲍勃告诉她的最终结果所暗示的对约束的约束，因为来自Bob的唯一其他信息是Bob知道Dams的值，因为某些人在k-j 1到k-j 10之间。功能E_a是随机的，所有10种可能性同样可能。

鲍勃知道什么？ 他知道y_j(这是x)，因此知道z_j。 然而，他没有关于其他祖的价值的信息，并且通过查看爱丽丝发给他的数字，他无法判断他们是否是z_u或z_{u 1}。

这尚未完成论证，因为Alice或Bob可能试图通过进行更多计算来弄清楚对方的价值。 例如，Bob可能会尝试随机选择一个数字t并检查Ea(t)= k-j 9; 如果他成功了，他就知道y9的值为t，并且知道z9的值，这使他能够找出ige;9。这将是Bob不应该找到的额外信息，如果 ige;j是前一个结论的结果。 因此，还必须在正式定义中包括，不仅参与者不会因协议规定的交换而获得信息，而且他们也不能在合理的时间内进行计算以获得该信息。 在3.2节中给出的正式定义中，我们将精确地定义它。

人们可能已经注意到，某一方可能会因为偏离商定的协议而在此过程中作弊。 例如，Bob可能会在最后一步向Alice撒谎并告诉Alice错误的结论。 有没有办法设计一个协议，使成功作弊的机会变得非常小，而不会泄露i和j的值？ 我们将在第3.3节中表明这是可行的。(请注意，这比Shamir et al。[5]中的心理扑克协议中使用的可验证性要求更强烈。)

根据不同的原则，我们还有两个针对百万富翁问题的解决方案。 其中第一个假设Alice和Bob各自拥有一个私有单向函数，其中这些函数满足通信属性，即E_aE_b(x)= E_bE_a(x)。 另一种解决方案利用Goldwasser和Micali发明的概率加密方法[2]。

3.2 一般问题的模型

由于这三种解决方案的安全性基于不同的假设，因此必须为每种解决方案指定精确的模型。 在这个摘要中，我们只给出与第一个解决方案相对应的模型。

为简单起见，我们将仅给出f为0-1且m = 2(Alice和Bob)的情况的定义和结果。 将结果推广到一般m将在第5节中简要讨论。一般情况的证据涉及额外的技术复杂性，并且存在额外的安全性考虑因素，例如在2人案例中不存在的可能的“共谋”。

协议。假设Alice具有公共单向函数E_a，其反函数D_a仅为Alice所知;类似地，Bob有一个公共Eb和一个私有逆D_b。假设E_a和E_b独立地和随机地从Q_N中抽取，所有可能的1-1的集合在N位整数上的函数上。用于计算函数f(i，j)的协议A准确地指定Alice和Bob应如何通信如下。 Alice和Bob交替发送字符串。每次Bob完成传输后，Alice都会检查她目前所拥有的信息，该信息由一系列字符串alpha;₁，alpha;₂，...alpha;_t和弦间的一些关系(例如E_b(alpha;₃)=alpha;₉，alpha;₈的奇数为1);根据迄今为止在她和Bob之间传输的比特，该协议规定了她应该如何计算私人字符串alpha;_{t 1}，alpha;_{t 2}，.... ，alpha;_s，其中每个新字符串alpha;_u是较早字符串的函数，或者是形式为E_a(y)，E_b(y)或D_a(y)的函数，其中y是已经获得的字符串。选择应用哪种函数或是否评估E_b或D_a一般是概率性的，即她将决定评估E(4)，或者根据某些投币结果计算alpha;₂ 3alpha;₈。完成此计算后，她将向Bob发送一个字符串，然后再次对该字符串进行概率选择。现在轮到Bob计算字符串并根据协议发送字符串。我们同意有一个特殊符号，其外观意味着协议执行的结束。到那时，协议有一个指令，让每个参与者私下计算功能值f。最后，我们要求在协议中，Bob和Alice对E和D的评估总数由O(N _k)限制，其中k是预先选择的整数。

隐私约束。 令ε，delta;gt; 0，并且f(i，j)是0-1值函数。 假设最初所有(i，j)值对都是相同的。 假设Bob和Alice根据协议忠实地执行计算。 最后，Alice原则上可以根据函数的计算值v和她所拥有的字符串，计算j值的概率分布; 叫这个p_i(j)。 如果满足以下条件，则称协议满足(ε，delta;) - 隐私约束：

1. p_i(j)= (1 O(ε))/|G_i|表示jisin;G_i，0其他，|G_i|其中G_i是j的集合，其中f（i，j）= v
2. 如果Alice后来尝试用不超过O（N_k）的E和D的评估进行更多的计算，那么在概率至少为1-delta;的情况下，她仍将在j上获得上述分布。
3. 上述要求对Bob也是如此。

定理1对于任何ε，delta;gt; 0和任何函数f，存在用于计算满足(ε，delta;)隐私约束的f的协议。

当(i，j)的初始分布不均匀时，可以考虑更一般的情况。 我们不会在这里讨论。 在第4节中，这成为概率计算的特例。

3.3 其他要求

(A)复杂性。 如果i，j的范围n变大，那么之前给出的百万富翁问题的解决方案将变得不切实际，因为传输的比特数与n成比例。 一个有趣的问题是，确定任何协议计算满足(ε，delta;)隐私约束的f所需的最小比特数。 可以想象，有些功能在没有隐私要求的情况下很容易计算，但在额外的隐私限制下变得不可行。 幸运的是，我们可以证明事实并非如此。 设A是一个协议，让T(A)表示当使用A时Alice和Bob之间交换的最大比特数。

定理2.令1gt;ε，delta;gt; 0且f(i，j)为0-1函数。 如果f可以通过布尔电路计算大小为C(f)，则存在满足(ε，delta;)隐私约束的协议A计算f，使得：T（A）=O(C(f)log(1/(εdelta;))。

实际上，如果f可以在时间S由图灵机计算，那么可以实现协议，使得Alice和Bob都具有图灵机算法来执行具有时间限制的O(S log（1/εdelta;）)的协议。

然而，存在需要在具有隐私约束的Bob和Alice之间传输指数多位的功能。 设Fn为0-1值函数f（i，j）的族，其中i和j为n位整数。 显然，在没有隐私约束的情况下，最多n位传输信息可以计算f（参见Yao [7]进一步讨论）。

定理3.设1gt;ε，delta;gt; 0固定。 假设f是Fn的随机元素，那么用（ε，delta;） - 隐私约束计算f的任何协议A对于所有大n必须具有T（A）gt; 2n / 2。

（B）相互怀疑的参与者。 到目前为止，讨论假设Bob和Alice遵守商定协议规定的规则。 如果他们中的任何一方为了获取更多信息而欺骗另一方以获得错误答案会怎么样？ 确实，根据我们的协议，如果之后有一个验证阶段，双方都需要披露他们的所有私人计算，那么任何作弊行为都将被发现。 但是，这将迫使双方揭示其变量。 正如稍后将要提出的申请中所表明的那样，这有时可能是一个严重的缺点。 以下结果将表明，人们可以阻止作弊，而无需要求揭示变量。

由于协议永远不会禁止Alice（或Bob）表现得好像她有一个不同的变量值i，协议可以实现的最多是确保这是Alice（或Bob）可以做的唯一作弊。

定义1.考虑执行协议的实例。 我们会认为这是Alice的一次成功作弊，如果Alice没有与i的任何值一致，但Bob没有检测到它。 鲍勃的成功作弊被类似地定义。

定理4.令1gt;gamma;gt; 0

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

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

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