摘要

本文通过公开讨论提供了隐私放大的一般处理，Bennett，Brassard和Robert为特殊情景引入了这一概念。 隐私放大是允许双方从公共随机变量中提取秘密密钥的过程，窃听者具有部分信息。 双方通常对窃听者的信息一无所知，只不过它满足某种约束。 该结果可以无条件地保护秘密密钥协议协议和量子密码，并且它们在窃听和广播信道上产生结果，从而大大加强了保密容量的定义。

介绍

放大是从大量仅部分秘密的共享信息中提取高度机密的共享信息（可能用作加密密钥）的艺术。让Alice和Bob给出随机变量W，例如随机的a比特串，而窃听者Eve学习相关的随机变量V，提供至多t <n比特的关于W的信息，即H（WIV）>=N-T。除了满足该约束以及可能的一些进一步约束之外，Alice和Bob通常不知道分布PVW的细节。他们可能知道也可能不知道Pw。 Alice和Bob希望公开选择压缩函数g：（0，l）“+（0，l}”，这样Eve的关于W的部分信息和她关于g的完整信息给出了关于K = g（W）的任意少量信息给出所有Eve的信息，得到的K几乎均匀分布;因此可以安全地用作加密密钥.Alice和Bob可以提取的秘密的大小T取决于，但概率可以忽略不计（g的可能选择）。 Eve的可用信息种类和数量。假设W是一个随机的n比特串，各种可能的场景要考虑Eve可以获得1）t W的任意比特，2）t W的任意奇偶校验3）将n比特串映射到t比特串的任意函数的结果，或4）通过满足h（e）= 1-t / n的比特错误概率E的二进制对称信道发送的字符串W，以及因此具有容量t / n，其中h（.）表示二进制熵函数。我们提出了一个更一般场景的解决方案，其中所有上述都是特殊情况。在这样 场景中，允许Eve指定任意分布PVW（Alice和Bob未知）受唯一约束条件R（WIV = w）2 n - t具有高概率（超过值U），其中R（WIV = w）表示W的二阶条件R＆yi熵[151，[27]，给定V = w（参见第IV节）。对于任何s <n-t，Alice和Bob可以通过公开选择压缩函数G来提取秘密密钥K = G（W）的T = n-t-s比特，同时保持Eve的关于K的信息在指数上小于s。现在这是一个随机变量）从一组合适的地图随机变成（0，l} nt - sM。正好，我们证明了H（.K（G，V = w）2 T - 2 - “/ ln2，只提供R（WJV = w）2 n - t。显示该结果不能推广到允许Eve在没有进一步限制的情况下获得香农意义上的任意信息位：H（WIV = w）2 n -t对PVW的限制不足以实现隐私放大。

在下文中，我们提供了本研究的动机和背景。密码学的一个基本问题是由Alice和IBob这两方生成共享密钥。在大型网络中，假设在需要密钥时出现安全信道（例如可信信使）在Alice和Bob之间可用是不切实际且不现实的。因此，我们考虑一种情况，其中Alice和Bob仅通过不安全的信道连接：Alice和Bob之间交换的所有消息都可以被窃听者Eve完全接收。但是，在整篇论文中将假设Eve不能通过插入或修改消息来主动篡改频道，而不会被检测到。这种假设的有效性可以通过众所周知的无条件安全认证技术来保证[32]，这里不会讨论，只要Alice和Bob最初共享一个短的无条件安全密钥。假设存在用于认证目的的这种短密钥不会使密钥协商协议变得无用：这样的协议可以被解释为允许短密钥的任意无条件安全扩展。 Otheir意味着，例如电话线上的说话人识别，也可以在实践中使用。

在本文中，我们有兴趣证明加密方案的安全性，特别是密钥协商协议。 密码系统安全性证明的重要性在很大程度上取决于三个问题：1）安全性的定义有多强？ 2）关于窃听者可用信息和计算资源的假设有多现实？ 3）系统有多实用？ 对于大多数以前可证明安全性的方法，安全性的定义或关于窃听者信息的假设都不令人满意，或者系统不实用。 例如，完全安全的一次性密钥使用不切实际的长密钥。 此外，从Alice到Bob的频道比从Alice到Eve [16]，[33]的频道噪声更小的类型的假设在许多应用中是不现实的。

我们不会对窃听者的计算能力做出任何假设：我们将考虑无条件或信息理论而不是计算安全性。 这有两个原因：第一，没有任何假设的结果更强，第二，证明破解密码系统的计算难度的任何合理性似乎完全超出了当前计算复杂性理论和密码学研究的范围。 请注意，允许Eve使用无限的计算能力排除公钥加密[17]作为秘密密钥协议的可能技术。 当然，公钥加密是在大型网络上实现安全性的重要工具，但是对于Eve的计算能力没有任何合理的限制，可以为任何公钥密码系统提供安全性证明。
密码系统最安全的安全概念是由Shannon定义的保密[28]。 当且仅当明文消息M在统计上独立于密文C，即I（M; C）= 0时，系统是完美的.Shannon证明了悲观结果，即只有当秘密密钥K处于时，才能实现完美保密。 至少与明文消息M一样长，或者更准确地说，当H（K）2 H（M）时。 然而，这个证据是基于这样的假设：窃听者可以获得与合法接收者完全相同的信息，除了秘密密钥K，并且这种假设通常是不必要的限制。

例如，当信息以量子系统的非渐正状态编码时，例如单个光子的非正交偏振，不确定性原理防止窃听者 - 或甚至预期的接收者 - 从量子信号中提取完整信息。 这一事实，以及在不干扰其非局部相关性的情况下对纠缠量子态进行局部测量的相关不可能性，可以被用来限制密钥协商协议中的窃听者信息[21,141，[91]，以及防止过多的轻率信息流动 在不经意转移的协议中[31]和两个合作但相互可疑的各方之间的比特承诺[lo]。 所有这些量子密码协议，特别是当用真实设备[2]，[231，[26]，2301实现时，产生部分秘密信息，需要在其被充分利用之前进行清理（例如，通过隐私放大）。

同样，Maurer [24]提出了一个密钥协议协议，使用卫星来广播在地球上无法完全可靠接收的随机比特，即使使用非常昂贵的接收机技术也是如此。 人们可以想到许多其他情况，其中各方看到的信息是相关的，而不会让窃听者完全了解所有其他方的信息。 令人惊讶的是，秘密密钥协议不要求Alice和Bob的信息之间的关联强于Alice和Eve或Bob和Eve的信息之间的关联。

隐私放大及其实现的关键协议具有广泛的加密应用程序。 本文讨论密钥协议，但当然可以通过使用生成的密钥作为众所周知的一次性密钥中的密钥流，将无条件安全密钥协商协议转换为无条件安全加密方案[28]，[31]]。 此外，隐私放大在各种两方协议中发挥着重要作用，即遗忘转移[3]和比特承诺[lo]。

最后，无条件安全认证需要共享密钥[32]，与一次性密码加密一样，它会占用密钥位并使其不适合重用。 因此，我们看到无条件安全的身份验证和隐私放大可以互相受益：前者为后者服务，以确保Alice和Bob之间的公开讨论不被Eve篡改，并且一些产生的秘密共享密钥位可以是 用于后续身份验证。 爱丽丝和鲍勃之间的一个简短的初始密钥是必要的，以启动这个系统，避免明显的恶性循环。

本文的结构如下。 第11节讨论了无条件安全密钥协议，其中隐私放大问题是有动机的。 在第111节中，描述了本文考虑的一般隐私放大场景，并讨论了窃听者可用的各种类型的辅助信息。 通过通用散列的隐私放大和本文的主要结果在N节中给出。在第五节中，说明了密钥的可实现大小与理论上限之间的差距，并在第六节中说明了弥补这一差距的技术。 被呈现。

无条件地解决秘密密钥协议