密钥协议和安全计算的交互

1、密钥协议和安全计算的交互摘要通过互动的公共通信通道，我们分析了多方的相关数据，仔细研究了信息理论密钥（SK）和安全函数计算。我们主要的研究是SK的长度上限，通过综合多方SK协议减少二元假设测算推测来得出。建立在这个基本结果之上，我们得到了新的SK协议的认识。此外，将无视传输协议和某些承诺协议与SK协议相关联，我们得到了交互的结果。最后，得到了受信方集体数据函数可行性安全计算的必要条件，那就是使用一个本身不会泄露价值功能的交互式的大众媒体传播。在很多情况下，我们加强和改善先前已知的交互界定，得到的结果是单发的并且只是用给定的相关观测的联合分布。对于这个例子，当相关的观察值由独立分布序列组成时，我

2、们获得了更精确的的先前版本的交互。关键词假设测算，密钥协议，安全双方计算，单发交互。1.介绍信息理论的密码学与相关的随机观察各方的实用性有关。如果同行者的观察是相互独立的，那么多方密钥（SK）和安全计算是可行的。事实上，SK协议并不可行，即使是观察一些独立分区。作为对这一原则的一个扩展，我们可以预计，加密原语与“多远”观察是一个联合分布，呈现出观察独立性（在某些分区组内）。我们形式化这一启发式原则，利用它限定使用相关资源的效率来实现SK协议和安全计算。我们报告了单发交互结果，特别的，我们不认为当事人的观察结果是由一个长的独立同分布（IID）随机过程序列所组成。在多方SK协议中，观察相关随机变量

3、（RSV）的同行者寻求达成共享随机比特并隐藏访问相关信息的偷听者。同行者可以在一个无声的公共频道内相互交流，但是传送的通信将可能被偷听。推导我们交互结果的主要工具是减少SK协议二次假设测算的内容。对我们的主要思想进行一下说明，考虑一个双方的例子。当偷听者仅仅观察合法双方之间的通信而不观察任何额外的信息时，很显然，如果合法方的观察是独立的，那么SK就不能生成。根据“多远”所生成的SK长度上界是观察方的联合分布，通过分布呈现他们观察的独立性。具体的说，对于这个特殊的情况，我们得出SK的最大长度s的上界是鉴于型误差的概率小于，当测试的零假设代替时，是型的最优概率误差。这个代表和之间的距离。同样，在一

4、般情况下对于任意数量的相关方信息的偷听者，我们在定理3中的结果依据观察方联合分布之间的距离界定了密钥长度，当条件为偷听者的信息时，当事人的预测条件就独立成一些分区。这个界定是对上述启发式原理的显示，被称为约束条件独立测试。我们所运用的的方法将SK协议与二次假设测算进行了结构连接。这个方法在参考文献52中有所体现，对信道编码和二次假设测算进行连接是用来建立一个拥有极佳上限的信道码率。当然，我们的上界让人想起了在参考文献74中提到的缠结量子态的测量，即国家的密度矩阵之间的最小距离及其分状态。缠结的措施在参考文献74中被证明是一个上限蒸馏的缠结，其中后者是最大比例的最大缠结态，可以使用精华蒸馏过程。

5、使用我们的基本结果，我们得到新的SK协议。同时，为了确保双方的安全计算，可以减少SK的无视传输协议和承诺协议。在许多情况下，我们加强和改善先前已知的结果，将我们主要的贡献总结如下。A. 密钥协议对同行者来说，SK密钥协议相关的观察问题是较好的研究。这一问题是由Maurer、Ahlswede和Csiszar引入，他们考虑到了一个例子：同行者去观察IID序列。但是在某些应用程序中，考虑由相关RVS实现结果所引起的观察值是很有趣的。例如，在生物识别等应用程序和硬件验证方面，对包括生物的不同版本和硬件签名的相关观察分别进行了记录登记和分阶段验证。为此，Renner和Wolf推导出了SK的长度上限，它由

6、双方观察一个单一的RVS时通过单面沟通所产生。对于IID设置来说，多方SK协议的问题在参考文献16中进行了解释。在本次研究中，我们通过观察一个单一的RVS考虑了多方SK协议问题。我们的条件独立测试界定是一个单发的SKs长度上限，可以由多方使用公共交流互动观察相关数据所产生。与在参考文献60中仅限制与单向通信方通信不同，我们允许任意多方的互动交流。我们的渐进界限是紧密的，其在IID中的应用可以恢复一些之前所知的SK率渐进界限。事实上，我们加强了先前已知的渐进结果，因为我们不必考虑SK协议或保密渐进指数中的错误。（参见第四节详细讨论）B. 双方的安全计算双方的安全计算问题在参考文献83中进行了介绍

7、，双方寻找一个可以不必知道双方数据就可以计算出他们的集体数据的函数。对这个普遍问题进行了几个实例研究。我们考虑了转移（OT）和承诺（BC）这两个问题，他们是构成双方安全计算的基础元素。OT是双方之间信息传输模式“发送方不知道收件人是否收到信息”。在这篇文章中，我们考虑到了二分之一的OT问题：第一方观察两个字符串K0、K1的长度，第二方寻求Bth串的值。对于这个问题我们需要用一种使B和均隐含的方式完成，简单说这个问题就是安全函数计算的核心。任何安全函数计算任务可以反复使用基本协议完成。不巧的是，信息理论安全OT在没有额外的资源时是不可行的。值得庆幸的是，如果双方共享一个嘈杂的通信通道或者如果他们

8、注意到了相关的随机性，OT就可以完成。在本文中，我们考虑了后者情况，作为额外的资源，双方遵守相关的和。基于减少OTSK协议的相关参数，我们所得到的OT的上界长度可以完成给定的，。总的来说，由此获得的界限比在参考文献79里的更严格。此外，我们绑定到应用程序IID的观测表明OT长度的上界在参考文献2、48中很大。现在让我们看看BC问题。其中第一个实例介绍了Blum在7中所提到的电话抛硬币问题，这是在双方互不信任的情况下发生的。有些承诺协议分为两个阶段。在第一阶段提交方生成一个随机比特串K“抛硬币”。随后，双方互相沟通，第一阶段结束。在第二阶段，提交方揭示K。承诺协议必须禁止提交方欺骗或者在第二阶段

9、改变K。在OT这个例子中，信息理论安全BC没有额外的资源是不可能的。我们考虑这样一个版本，双方使用公共交互通信观察x1,x2，从而实现信息安全。目标是最大化所提交的字符串K的长度。通过降低SK对BC的协议，我们获得了一个BC长度的上限。另外，在IID观测的情况下，我们得到了一个强大的BC能力的交互，后者是BC长度的最大值。C. 受信方的安全计算在不同的方向，我们在下面的安全问题函数计算中进行叙述（一个早期的版本，看50）：观察相关数据的多方，寻求一个可以计算他们集体数据的函数。为此，他们通过公共通信信道交互沟通，这被认为是身份验证和零错误。这个要求函数值对访问交流的偷听者是隐藏的。那么这样一个

10、给定函数的安全计算什么时候是可行的呢？相比上面所讨论的传统的安全计算问题，这个设置更适合于一下应用，例如：传感网络，合法方是被信任的并且可以通过共享信道自由提取任何相关方的信息。通过使用有条件的独立测试绑定，我们获得了存在一个通信协议的必要条件，允许当事人可靠的恢复一个给定函数的值，同时保持这个值对访问的偷听者是隐蔽的。在参考文献69,匹配了安全计算性的必要和充要条件的情况下推导出了给定函数的IID观察值。相比之下，我们的安全计算性的必要条件是单发，不依赖于IID观察值。D. 文件轮廓下一部分介绍一下在研究中使用到的基本概念，条件独立测试边界在第三部分导出。在随后的三个部分中，我们提出了这个界

11、限的隐意：第四部分详细介绍了SK的能力；第五部分描述了OT和BC问题的结果；第六部分描述了受信方安全计算问题的结果；最后一部分简短的讨论了可能的扩展。E. 符号为了简便起见，我们使用缩写SK，RV，IID分别表示密钥，随机变量，独立同分布；复数形式通过加s来实现。RVs用大写字母表示，相应的区间集用书法字母表示。RVU的分布规律是由PU给出的，当不会混淆时我们标注了下标U。当事人的集合1,.,.,m由M标识。作为RVs集U1，.,Um和M的子集A，UA用来表示RVsUi，iA。Un表示nIID 就是RVU的重复次数。Pn表示由P所生成的nIID重复次数的分布。文中出现的所以对数参见基础2。.导

12、论A. 密钥考虑使用互动的公共通信SK协议m，第i个当事人观察在一个有限集Xi,1<i<m,上的RV离散。通过这些观察，双方在通过公共通信通道交互沟通时可以被偷听者介入，而且还能另外观察像RVs（XM，Z）这样的RVZ。我们假设沟通无误，并且各方从其他方接受沟通。另外，我们假设公共通信可以进行验证且偷听者无法篡改它。具体来说，通信循环交互发送r。在第j个循环交互中，1<j<r,第i个当事人发送Fij(观察值Xi，局部随机生成的Ui,先前观察的通信之间的函数) 整体的互动沟通F11，.,Fm1,.,F1r,.,Fmr是由F分配的。使用局部的观察和交互沟通，双方达成一致的S

13、K。通常，SK是RVsK1，.,Km的集合，第i个当事人给定Ki,同意率接近1并且对偷听者隐藏。第i个当事人计算函数Ki(Ui,Xi,F)，如果满足下面两个条件，RVs K1,.,Km在给定一个K时就构成了一个范围（，）-SK：Punif是K的均匀分布，d(P,Q)是P和Q之间变化的距离，由下式得出： 上面第一个条件是可靠的恢复SK，第二个条件是保密。在这项工作中，我们使用以下的式子来替代SK的定义，方便的结合了可恢复性和保密条件：如果满足(3)上述的RVs K1,.,km组成了拥有常数范围K的-SK：事实上，上述的这两个定义联系很密切。命题1：给定0<,<1,如果KM在（1）式下

14、组成（，）-SK，那么它在（3）式下组成（+）-SK。相反的，如果KM在（3）式下组成-SK，那么它在（1）和（2）式下组成（，）-SK。因此，通过组合在8中的定理，复杂的加密协议使用这样的SKs代替原始的SKs是安全的。我们对描述-SK中log|K|的最大长度很感兴趣。定义1：给定0<<1,在给定常数范围K时，由表示-SK的log|K|的最大长度。我们的上界是基于有关SK协议问题的二次假设检测问题，下面我们将回顾一些在假设检测中会用到的基本概念。B假设检测考虑一个二次零假设检测问题P和对立假设Q，P和Q分布在相同的字母表X中。观察一个值xX,观察者需要决定生成的值是否为分布P或Q

15、。为此，观察者应用随机测试，测试的一个条件分布在0,1给定的观察值是xX。当xX是观察值时，测试T选择零假设的概率是T（0|x），对立假设的概率是T（1|x）=1-T(0|x)。对于0<<1, 与型中由（P,Q）表示的最大下界相比，型的误差概率小于，我们记录了量（P,Q）的两个重要属性。1） 数据处理不均：令W为从X到Y的随机映射，对于每一个xX,W(.|x)在Y中都有一个分布。然后 2） Stein的引理：对于每一个0<<1,都有D（P|Q）是kl散度，公式如下：我们约定： C（P,Q）评定方法的备注我们讨论一下（P,Q）评定方法。注意，（P,Q）在（4）中的表示是一

16、种线型规划，用于解决观测空间规模的多项式复杂性。一个简易的操作生成了更容易计算的范围：当P和Q符合IID RVs时，在（7）中的尾数概率可以直接进行数值计算或者可以用Berry-Esseen定理近似近似计算得出。另一方面，当P和Q符合马尔科夫链时，可以进行尾数概率的数值计算。对于这种情况，在（P,Q）中的易于计算和渐进约束的绑定在77中可以建立。同时，通过设置的当>1时Resyi的散列值可以得出，式子在61中给出下面是所获得的（P,Q）的简单界定：对于量子观察中的变种界定在49,Th,1中进行了记录。一个典型的例子，界定必须遵从简单的证据，如下：由Ay表示的集合x:logP(x)/Q(x

17、)<y。因此，对于>1,进一步暗示了。（8）受（7）的影响，一般来说，当（8）的界定不是很小时，它的推论是遵循Stein的定理的。 最后，我们总结当条件成立时，P下1的可能性是满足的，这一界定在（7）中有显示给定两个RVs X和Y，保密信息理论的核心问题是：有多少无偏独立位可以从X中获得？IID底层分布时，最佳的提取比特率可以依据香农熵和给定的H(X|Y)表示。然而，对于我们的单发设置，在5860中引入的光滑的最小熵是一个相关的随机测量，依据其他变化的综述。我们也回顾剩下的散列理论，解决一下在上面所提出的光滑的核心最小熵的问题。同时，对于改变最小熵的测量手册，我们定义了光滑最大散度

18、它满足不均的数据处理。定义2：P的最小熵被定义为：对于Pxy和Qy的分布，Pxy的最小熵为Qy提供的条件如下：最后，Pxy的最小熵为Y给定的条件如下：来自最大散度Dmax(PQ)的等式是正的，并且当且仅当P=Q是，等式为0.条件最小熵的替代形式是在41被第一次提出，首次提出了最一般的量子设置并显示了Hmin(PXY|Y)相对于-log的推测X,Y的平均可能性的条件。然而，11中的最初的形式更适合我们的目的。最小熵的定义和最小熵的条件在所有低能的，非负函数Pxy都是可行的 Pxy如下：我们需要这个扩展和平滑的概念为接下来的定义提供更严谨的界定。定义3：给定的>0,Y一定时，-smooth对

19、应的Pxy的条件最小熵被定义为：当Y时恒定的，-soomth的最小熵由来表示。现在我们陈述剩余的散列引理，就是从中提取出的隐藏Y的独立的X。引理2：给定一个联合分布Pxy,对于每一个0<2<1,0<,存在一个映射K： 。 最后，我们回顾光滑最大散列，其在18中作为量子设置被引入。接下来定义的平滑方法余18的略有不同，但是是适合我们的目的的。定义4：P和Q之间的最大散列被定义为在的条件下，0<<1, P和Q之间的最大散列被定义为接下来将被使用的两个平滑最大散列属性是：1） 不均数据处理：对于每一个随机映射W: 只要 2） kl散度的收敛：对于IID分配的Pn和Qn,

20、如果不等条件是不存在的。因此，这足以证明一点，在假定条件下D（P|Q）是限定的。为了这个目的，考虑。对于一个序列和xX的元素，通过N(x|x)来表示x在x里的发生次数。然后每一个序列满足注意对于足够大，因此，在假设时，最后一个不等式来自（14）.对于其他方向的不等式，如果我们给定一个并且 那么， 对于所有的n都足够大，这进一步的表明，存在一个 实现的确，如果不这样的话，那么对于所有的与在（15）中进一步显示的是相矛盾的。因此，对于例子这里存在，使得，因为，所以上述等式的右边也是无穷的。另一方面，如果D(P|Q)是限定的，使用（14），对于序列上述等式的右边是有界的。.有条件的独立测试本文的交互

21、结果是基于最大长度S的，在这里我们展示一下这个结果。考虑M中的一个集合划分，如果底层分布的观测值PXMZ四条件独立的跨分区Z，那么SK的长度可以生成为0。我们的方法就是限制SK的生成长度，依据“多远”是来自另一个分区的分区PXMZ呈现XM，两个分区的亲密度是测量得到的。特别的，对于一个划分，让成为所有划分的一部分，因式分解如下：定理3：给定0<<1,0<<1-,M的一个划分对于所有的备注1：Renner和Wolf得到了一个对于SK长度的界定，可以由使用同一交互通道的双发产生。这个界定在定理3中的对比是不可能实现的，因为前者包含辅助的RVs并且很难评估。备注2：对于m=2

22、,Z=常数，SK长度的下界在定理3中与Polyanskiy的meta-converse紧密相关。此外，信息M进行点对点通信，代码的可靠传输产生一个发送者和接受者；SK的长度可以由定理3来界定。然而，结果略低于meta-converse，在最优规模传播代码64中不产生三阶渐进词。备注3：下面的定理3的证据仍然是有效的，即使是用一般的条件去取代保密条件 ： 我们证明定理3的潜在关键理念是一个的下限，对于拥有观察空间KM的二次假设检测，零假设P给出了：对立假设Q给出了：即，测试的问题是K1，.,Km是否构成了完美的相关统一随机性和他们是不是互相独立的。引理4：对于在（18）（19）中的和，对于所有的

23、0<<i都有证明：考虑对数似然比的极限，给出测试可以进行的可行范围对于这个测试，型的错误率界定如下另一方面，型错误率如下，只要组成KM的元素满足第二个等式就成立。内部和可被进一步的展示如下上述第一个等式成立时,第二个等式成立时遵循Holder的不等原则。综合（21）（22）得出因此我们有一个型错误率小于的测试，型的错误率在（20）中有所展示，因此，。证明结束。在（18）中的PKM对应于一个被m个同行者分享的完美的密钥，接下来的结果扩展了引理4,中的关键值KM、F通道、被观察的偷听者的编带信息Z和对应于SK-M的零假设PKMZ。引理5：对于每一个0<<1-,每一个都有 对

24、于联合分布 是 的临界，并且是对应的临界。当然我们需要下述68交互通信的基本特性来贯穿整篇文章。引理6：给定一个和交互式通信F，得到如下式子：所以在交互通信附加条件独立的观察结果仍然成立。特别的，如果那么引理5的证明：证明简单的修改了引理4。首先记录引理6，是F确定的函数，这里有。因此，引理4在Q作用下有分布对于每个，对于每个（f,z）有，形如： 我们考虑如下的测试，对于一个二次假设检测问题，有零假设和替代假设：对于一个观察者，如果且有其他的替换我们接受零假设。使用公式（24）型的错误性计算如下：通过（25）型的错误性计算如下：。 最后，我们利用零假设、替代假设进行试验考虑了假设检测问题。显然

25、，型错误率不变。另外，在（3）所考虑的安全条件下，型的错误率在不超过时将增加，这一点已经得到了证明。 定理3的证明：我们首先考虑在每一个元素中的划分，对于1<i<m,对于这个例子，由定理5和不等式（5）数据处理产生：并且。对于每一个1<<1-,有扩展（26）得到一个划分，我们声明，当地i个同行者观察时（1<i<）,一个-sk的原始模型与m方都会产生一个与-sk长度相同的模型。现在只需要证明上述声明。为此，对于原始的模型给定一个-sk我们给-sk定义一个新模型，如下：在原始的模型中任何一个在沟通时生成的KM，双方运行协议。对于在新模型中的每个同行者i，我们选择

26、一个代表；具体地说，让i0成为中最小的部分。在新模型中一个当时给定，由如下分布表示单调性证明如下：证明完毕。.密钥容量的隐喻对于SK协议问题，一个感兴趣的特殊的例子当观察者组成的长度为n的IID系列，第i个观察者和像RVs的偷听者是IID。对于这个例子，可知能生成SK对n的长度比例；SK利率的最大值被称为SK容量。为了展示这一部分的总长度，我们需要借助于在（1）（2）中给出的的原始定义。定义1的方式表示了的最大长度。它来自于命题1。定义5：给定0<,<1,容量如下定义：当是IID并且1<t<n,有同分布，SK容量的极限定义如下：对于这个例子，当偷听者没有观察到任何边界信

27、息时Z=常数，双方的SK容量由Maurer、Ahlswede和Csiszar给出。之后，当Z=常量，SK容量在多方模型中由Csiszar和Narayan给出。SK容量的很多下界在116172644中给出。在这一部分，我们得到了双方SK容量的单射版本，这是在这个例子中最容易理解的。另外，对于多方同行者，我们建立了一个SK容量的强交互，但我们并不能通过降低恢复能力需求或者安全需求提高SK比率。A 双方交互的结果在26中显示了在26里的假设依赖于是IID这一结论，并且不能应用于单射设置。下述的结果是27的单射版本，SKs进行了证明。定理7：对于0<,+2<1,对于每一个RV U都有通过推

28、论，我们得出了一个单射的版本并在27中扩展了下界，不需要最合适的渐进恢复机渐进安全性。推理8：对于0<,推论9：对于0<,引理10：令（K1，K2）在中取然后，对于每一个RV U，0<<1-2,有定理7的证明：让（K1，K2）在中取然后通过引理10和在（13）里的最大散度的数据处理，我们得到：通过剩余的散列引理，这里存在一个的映像在中得到的，满足因此，构成了X1，X2的，当偷听者观察（Z，U）时推论8由定理3得出。推论9的证明：推论8的结果应用了Stein的引理,遵循最大散列的收敛性。定理10的证明：通过定义和足以显示对于每一个映像T：0,1时，这里存在一个非负函数和一

29、个分布满足如下条件由给出，因为所以这是个有效的非负函数。另外，因为我们得到了（29）的公式如下：第一个不等式是三角不等式，最后一个不等式根据安全条件（2）和假设（28）得到。接下来将定义如下：得到：B 多方同行者的强交互当偷听者得不到边界信息时，我们分析一下m的终端例子。通过化简，SK对于多方的容量由Csiszar和Narayan给出。另外，在等式右侧进行了显示的表达，展示了当m=2,3时它的紧密度。最后，对于任意的m的紧密度在10中进行解释；我们将所得的结果总结如下。定理11：SK容量的例子，当偷听者的边界信息Z=常数时得到，其中最小值是M的所有划分。这个由Maurer、Ahlswede和C

30、siszar提出的普遍的结果是建立于两个同行者之间的。定理11的交互部分依赖于当时。下面我们加强这个交互并将将SK率的下界在定理11中进行表述。特别的，对于，Z=常数，一个定理3对IID的应用是，因此使用Stein的引理我们得到如果SK率是无穷的。实际上，考虑一个，此时RV生成一个K1并且通过公共交互通道将它发送给其他的同行者。因为K是随意的，所以的长度结果是随意大的。因此，我们建立了如下的当Z=常数时，SK容量的强交互。推理12：给定容量给定如下：.双方安全计算的影响这一部分我们考虑双方的安全计算，在过去的三十年这个问题推进了密码学的研究。特殊的我们要考虑一下不经意的传输和一部分委托问题，这

31、是安全计算双方的基本单元。我们分析一下理论上的阐述：作为一个额外的资源，同行双方观察相关的和我们得出的逆命题是基于还原与SK有关的参数，并应用于了定理3。A. 常见函数最大值和充分统计量最小值B. 为了陈述我们的结果，我们需要常见函数最大值和充分统计量最小值的概念。常见函数最大值的概念在24中通过用随机变量X1和X2对常见函数进行测试进行了介绍。它对于安全的作用在82中有所强调。操作上对常见函数的X1和X2的最大值定义如下。定义6：当存在函数和时（例如），一个常见函数X1和X2是随机变量U。常见函数X1和X2的最大值，通过进行表示。事实上，Gacs和Korner提出了提出其有如下的等式关系：充

32、分统计数最小值的作用在82做了强调。定义7：X1给定的充分统计数X2是如下的一个随机变量U，存在一个函数U=g(X1)使得马尔科夫链成立，X1给定的最小充分统计数X2是每一个充分统计数U的一个函数。对于的精确的特征是存在的，并且遵循如下的等价关系;C 不经意传输假如同行者1生成可K0和K1，均匀的分布在同行者2生成B，均匀的分布在0,1，作为OT协议的输出。假定和B是互相独立的，OT协议的目的是让同行者2实现KB。另外，同行者i在i=1,2时实现。在协议中，同行者可以互相交流。通常，同行者可以使用当地的随机取样；为了简单起见，没有当地随机取样时就阻止协议进行。然而，如备注6所写，当当地随机取样

33、允许时，我们的结果依然有效。定义8：实现的协议组成了交互通信F，同行者2的估计值满足一下条件：当第二、三个条件对于同行者1,2安全时，上述第一个条件表示了OT的可靠性。表示了l的长度。 当潜在的观察者X1，X2组成IID的长度系列时，可得的线型关系n。称最大增长率为OT容量。 定义9：对于，的容量定义如下：然后，OT容量定义如下：本节的主要结果是一个上限。因此，我们恢复由和提出的上限。事实上，我们表明，上限是无穷的，并应用于，当观察双方相关时，OT是可行的。但是，任何一方都不应该有超越他人的有点，以及只有一部分当事人遵守相关的随机性是有用的，不能由另一方来决定。借鉴此启发式，对OT长度进行两种

34、界限是可能的，基于OT长度的联合分布所观察到的相关随机性PX1X2是一个没用的分配，无用分布的选择是两个不同的范围。对于第一个界限，我们考虑一个分布：使得X1和X2独立给出。对于这样的分布，一旦每个共享知识同行者分解出来就没有相关性OT了。在第二界限，我们认为V1 = MSS（X2 | X1）可以通过X2来确定。注意，对于这种分布因式分解成立时，这样的分布是无用的，因为OT的本质是由X2决定的。作为SK协议的情况，我们将使用测量两个分布之间的距离。事实上，我们通过减少SK协议来证明OT，对于这两个界限的消减是不同的。定理13：对于RVs和下列不等式成立:对于所有的有推理14：对于0<&l

35、t;1, (X1, X2)的容量OT满足：，。定理13的证明意味着要减少SK协议，（37）的界限是通过获得回收的KB作为SK，而（38）是由回收得到KB作为SK；我们注意到这两个反应作为单独的引理如下：引理15：考虑到双方遵守X1和X2的SK协议，分别与窃听者观察。给定一个协议，存在一个用于产生一个协议长度L的。引理16：考虑到双方SK协议，其中同行者1观察X1，同行者2观察(V1, X2) = (mss(X2|X1), X2)和所述的窃听者X2。给定一个实现长度为L的，存在用于生成长度为L的协议。备注4：底层的证明是对OT的协议的缩减，这是我们证明的延长，下面证明（）。相反，边界的证明依赖于

36、条款。下面我们举一个替代减少的论据证明（38）。备注5：在一般情况下，我们的界限比在79中提出的要大。例如，当观察者由IIDRVs的最大值组成时后者是松散的。此外，虽然（38）和（79）两者足以获得在推论14的结论，但是相反，（37）和79不能产生第一个推论14的约束。备注6：为了表述的简单起见，我们不容许进行随机的配方。然而，它可以很容易的包括到X1和X2中。由于我们的证明是基于减少SK协议的OT，经指出，mss(X2,U2|X1,U1) =mss(X2|X1)，随机性的可用性是不会代表我们对SK长的上限界定的，上述结果仍然有效，即使随机性可用。备注7：容量可以限定，而不需要 去作为C(X1

37、, X2)。然而，右侧（39）构成一个上限，只有当，建立这种约束的有效性。我们证明引理15和16如下，数据处理不等式（5）；推理如下斯坦因引理。引理15：设K作为KB的估计方2，下列协议生成。（1） 甲方1生成两个随机字符串K0和K1，甲方2生成随机比特B。双方运行OT协议，甲方获得KB的K个估计。（2） 甲方2通过公共频道发送B。（3） 使用B，甲方计算KB。 我们将证明所述的RVsKB，其中组成了。此SK的可靠性是有保障的，因为双方对KB的同意概率大于。为了建立保密制度，注意，如果同行者2向B发送，窃听者不能确定KB。另一方面，由同行者2在整体保密状态下观察同行者1的(K0, K1, X1

38、, F)会得到和B一样的分布。因此，相同的分布偷听者不能从(B, F)来确定KB。 形式上，由命题1和3注释的，只需要证明分布。引理16的证明：以下协议产生了一个长度为L的。（1） 同行者1生成两个随机字符K0和K1，长度为L,同行者2生成随机比特B，两方运行OT协议。（2） 根据观察者F，同行者2生成根据的采样。（3） 同行者2通过公共频道发送B。（4） 同行者1计算KB，同行者2计算。我们将证明所述的，组成了。这个协议用同行者仿真了，同行者1不需要关心B的价值，用控制会导致KB的估计值保留联合分布。 由命题1和（35），它足以说明：其中不等式使用（40），最后一个不等式使用Markov的关

39、系。D 比特委托双方遵循相关意见X1和X2，使用公共交互通信来实现信息安全理论BC。第一方一个报道，用于报告第二方的一系列结果。在以后的现阶段，通行者1可以检测同行者2。从形式上看，BC协议组成了两个阶段：提交阶段和揭示阶段。在提交阶段，同行者1生成一个随机串K，超过0, 1的L分布和均匀分布(X1, X2)。此外，双方相互使用交互式交互通信F。在揭示阶段，同行者1透漏了数据，即，它发送了和，声称这些是它的和的最初的选择。随后，同行者2适用于一个随机 测试功能，这里的，和。定义10：一个长度为L的实现的执行协议组成的交互交流F，在交流阶段被发送，值随机的测试函数T在揭示阶段使用，这时得满足以下

40、条件：对于RVs K和X1任何选择，X1具有相同范围集K和X1，满足：。上述的第一条件是一个可靠的状态，当同行者1可信时，BC是可信的，下一个状态是隐藏态。最后，结合（44）中的条件限制，同行者1可以在揭示阶段作弊。通过记录的最大L，使得协议实现长度为L的。对于长度为n的IID序列生成，的最大比率被称为BC容量。定义11：对于，对于的容量定义如下：BC容量定义如下：。Winter等人的结果如下，给出对于C(X1, X2)的简单公式。定理17：对于RVs X1, X2,让V1 = mss(X2|X1)，BC容量给定如下：。在本节中，我们提出了一个上限，这又导致了一个更大的BC容量。定理18:给定

41、对于和，得到下列不等式：对于，。推论19：对于0<,满足：，。定理19是由减少SK协议获得的BC，下面的引理得到了相应的约束。引理20:对于，满足，。备注8：当随机性不允许前面的讨论时，如之前，我们的结果不与当地的随机性的改变而改变。备注9：对于，下列的界定在56中推导得出：然而这种界定比定理18要牵强，在一般情况下，对于推论19是不充分的。如定理18所示，随着Markov关系X1V1X2和数据不等式（5），下面我们证明引理20。引理20的证明：给定一个长度为L的，考虑经双方观察X1和(V1, X2)的SK协议。为了生成一个SK，各方运行BC协议的提交阶段，即，同行者1生成，并发送F的交

42、互通信。我们展示了组成的交流密钥K。事实上，隐藏条件（43），对满足的保密条件（2）。从而，同行者2可以找到唯一获得的K的估计值字符串，它是与（V1，X2，F）兼容的。通常，会有这样的一个证明，存在，使最后，对于随机测试T，让，给定的函数 让。对于上述的，给出：，第一个不等式使用了定义，第二个不等式使用了Markov的关系，上述不等式要满足以下条件：我们通过观察一个简单的应用程序结束本节。对于一个详细的讨论56。例1：假设双方有一个长度为n的OT，以此作为一个资源，怎样建立一个长度为l的结构呢？由K0，K1指示的OT的串，并通过B的OT位表示同行者2。让和。需要注意的是，并且因此，通过定理18

43、和（10），我们可以得到。它显示了一个递增的损失然而56显示了一个增加的线型序列。.安全计算与可信方的启示 本节中，我们提出的安全功能计算问题的计算关系，值得信赖的同行者，如果当事人试图计算的函数，其观察所使用的通讯没有透露本身的功能的值。这是相对于处理的安全计算的第部分，其中所讲述的通信是安全的，但是同行者被禁止获得更多的计算函数的信息。此问题是在引入69时，被赋予了匹配的充分的条件。在这里，用定理3，我们导出的必要条件，例如：安全的可行性计算的一般性的意见。 在形式上，考虑在m 2时，同行者观察RVs X1, . . . , Xm由有限集可得值。在得出这些结果时，双方沟通交互可以可靠的计算一个函数。在以下的证明中，对于第i个同行者根据它所观察函数的估计G(i)形成基于函数的观察值Xi，局部随机化的UI和交互通信F即，。对于，这里存在一个定理，满足： 第一个条件的捕获的可靠性计算和第二条件的保密的协议。用于保密的F观察者必须懂得计算值函数的功能。我们力求表征计算函数g的。 在19,同行者观察并且寻求计算值。对于IID的，一个函数g，在同行者可以组成估计时是安全计算，这样。 定理21：对于渐进情况如上述所述，一个函数g在时是可以安全计算的，其中，。反正，如果一个函