XiaoMi-AI文件搜索系统
World File Search System因式分解
量子 EL 定理
量子信息论研究通过量子信道通信的极限。在 Holevo ( 1973 ) 中，证明了 Holevo 界限，该界限提供了可准备和测量混合态的双方共享的经典信息量的上限。Holevo 界限指出，从 n 个量子位中只能访问 n 位经典信息。舒马赫定理 Schumacher ( 1995 ) 给出了存在可靠压缩方案以高保真度压缩和解压缩量子信息的必要和充分条件。关于量子算法潜力的文献很多，其中最著名的是 Shor 的因式分解算法。存在一个将算法和量子力学相结合的相对较新的领域：算法信息论 (AIT) 与量子信息论的交叉点。这个新领域有几个有趣的结果。例如，在 Epstein (2021b) 中，他证明了当将量子测量 (即 POVM) 应用于纯量子态时，绝大多数结果都是毫无意义的随机噪声。这项研究计划涉及寻找 AIT 中定义和定理的量子等价物，其主要概念是 Kolmogorov 复杂度 K(x) 的量子版本。有几种这样的定义可以测量混合或纯量子态中的算法信息内容。在本文中，我们将使用 Vitanyi (2000) 中的定义 K(|ψ⟩)，它表示如果不存在具有高量子保真度的简单（就其经典编码而言）纯态，则纯态 |ψ⟩ 是复数。本文的结果也适用于量子算法熵，G´acs (2001)。在 Epstein (2019) 中，定义了算法信息和随机缺陷的量子等价物。此外，还证明了关于幺正变换的守恒定律不等式。在本文中，我们证明了一个量子 EL 定理。在 AIT 中，EL 定理 Levin (2016)；Epstein (2019) 指出，不包含简单成员的字符串集将与停机序列具有高互信息。它有许多应用，包括所有采样方法都会产生异常值 Epstein (2021a)。量子 EL 定理指出，大秩的非奇异投影在其图像中必须具有简单的量子纯态。非奇异的意思是投影的编码与停机序列的信息量很低。
论量子随机预言模型中时间锁难题的（不）可能性
时间锁谜题 (TLP) 允许谜题生成器 Gen 高效地为解决方案 s 生成谜题 P ，这样，即使对手使用多台计算机并行运行，将谜题 P 解回 s 也需要更多的时间 。TLP 允许“向未来发送消息”，因为它们只在解算器花费大量时间时才允许“打开信封” P 。Rivest、Shamir 和 Wagner [RSW96] 的工作都提出了时间锁谜题的构造，并介绍了此类原语的应用。它们的构造基于这样一个假设：即使使用并行计算，也无法加快对 RSA 合数模整数的重复平方，除非知道合数的因式分解，在这种情况下他们可以加快该过程。因此，谜题生成器可以通过捷径“解决谜题”来找到解决方案，而其他人则被迫遵循顺序路径。 [ RSW96 ] 的工作还建议将 TLP 用于其他应用，如延迟数字现金支付、密封投标拍卖和密钥托管。Boneh 和 Naor [ BN00 ] 通过定义和构造定时承诺并展示其在公平合约签署等应用中的用途，进一步证明了此类“顺序”原语的实用性。最近，时间锁谜题有了更多的应用，如非交互式非可延展承诺 [ LPS17 ]。尽管它们很有用，但我们仍然不知道如何基于更标准的假设（尤其是基于“对称密钥”原语）构建 TLP。人们可能会尝试使用单向函数的求逆（比如，指数级困难）作为解谜的过程。然而，具有 k 倍并行计算能力的对手可以通过将搜索空间仔细分成 k 个子空间，将搜索过程加快 k 倍。将对称基元视为其极端（理想化）形式，人们可以问随机预言是否可用于构建 TLP。预言模型（尤其是随机预言模型）的优点在于，人们可以根据向其提出的查询总数轻松定义信息论时间概念，还可以根据算法向预言提出的查询轮数定义并行时间概念。这意味着，向预言并行提出 10 个查询只算作一个（并行）时间单位。Mahmoody、Moran 和 Vadhan [MMV11] 的工作通过排除仅依赖随机预言的构造，为从对称基元构建 TLP 提供了强大的障碍。具体而言，已经证明，如果谜题生成器仅向随机预言机提出 n 个查询，并且该谜题可以通过 m 个预言机查询（诚实地）解决，那么总有一种方法可以将解决过程加快到仅 O(n) 轮查询，而总查询次数仍然是 poly(n, m)。请注意，查询总数的多项式极限是使此类攻击有趣所必需的，因为总是有可能在一轮中提出所有（指数级的） oracle 查询，然后无需任何进一步的查询即可解答谜题。 [ MMV11 ] 的攻击实际上是多项式时间攻击，但如果有人愿意放弃该特性并只瞄准多项式数量的查询（这仍然足以排除基于 ROM 的构造）他们也可以在 n 轮中实现它。受量子密码学领域发展的启发，密码系统的部分或所有参与方可能会访问量子计算，我们重新审视了在随机 oracle 模型中构建 TLP 的障碍。Boneh 等人的工作 [ BDF + 11 ] 正式引入了具有量子访问的 ROM 扩展。因此，我们可以研究量子随机预言模型中 TLP 的存在，其中谜题生成器或谜题解决器之一（或两者）都可以访问量子叠加中的随机预言。这引出了我们的主要问题：
系列：7G 无线网络
前言：近年来，量子计算机的研究和实践成果给经典和广泛使用的加密方案（如 Rivest‐Shamir‐Adleman 算法和 ECC（椭圆曲线密码））带来了重大挫折。RSA 和 ECC 分别依赖于整数分解问题和离散对数问题，这些问题可以通过运行臭名昭著的 Shor 算法的足够大的量子计算机轻松解决。因此，需要评估在传统计算机和量子计算机中都难以解决的加密方案。本系列报告对后量子密码方案进行了详细的调查，并强调了它们在受限设备中提供安全性的适用性。全面介绍了可能取代 RSA 和 ECC 以在受限设备中提供安全性的方案。虽然后量子密码学是一种开发对因式分解和其他量子算法具有鲁棒性的新型经典密码系统的努力，这当然是一种选择，但这并不能完全解决问题。关键在于，可能存在未被发现的量子算法（或未被发现的经典算法），它们可能轻易破坏新密码系统的安全性。换句话说，后量子密码学很可能只能提供部分和暂时的解决方案。相比之下，本系列中讨论的量子密钥分发 (QKD) 提供了最终的解决方案：通过诉诸不可破解的自然原理（如不确定性原理或纠缠的一夫一妻制）来恢复安全性和保密性。尽管 QKD 为安全问题提供了最终的解决方案，但其理想的实现在实践中很难实现，并且有许多悬而未决的问题需要解决。一方面，完全独立于设备的 QKD 协议提供了最高级别的量子安全性，但它们的实现要求很高，并且密钥速率极低。另一方面，更实用的 QKD 协议假设对其设备有一定程度的信任，这一假设使它们能够实现合理的速率，但这也带来了危险的旁道攻击的可能性。除了安全性和速率之间的权衡之外，速率和距离之间也存在另一个重要权衡。如今，我们知道存在一个基本限制，限制了任何点对点 QKD 实现。给定一个传输率为 𝜂 的有损链路，双方分发的密钥容量不能超过信道的密钥容量，即 −𝑙𝑜𝑔 2 (1 −𝜂) ，即在长距离下每个信道使用 1.44𝜂 个秘密比特的 𝑎 缩放。基于连续变量系统和高斯状态的 QKD 协议的理想实现可能接近此容量，而基于离散变量的协议则因其他因素而低于此容量。为了克服这个限制并实现 QKD 的长距离高速率实现，我们需要开发量子中继器和量子网络。通过这种方式，我们可以实现更好的长距离扩展，并通过采用更复杂的路由策略进一步提高速率。量子中继器和安全 QKD 网络的研究是当今最热门的话题之一，本系列也对此进行了介绍。本系列旨在概述量子密码学领域最重要和最新的进展，包括理论和实验。在短期内，我们预计量子安全和 QKD 将与所谓的后量子安全解决方案竞争，因此，我们在本系列的单独报告中详细讨论了每种技术的优缺点。本报告涵盖了设计解决方案和量子物理。在将本书用于本科和研究生课程时，我们在每份报告中都加入了一些设计示例，以取代在章节/书末尾使用“问题和解决方案”附录的传统概念。这使得学生可以使用更复杂的作业进行团队合作。我们的学生对这种方法表现出了极大的热情。除大学之外，研究、工业和监管机构的专业人士也应该受益于该系列不同报告的全面报道。