XiaoMi-AI文件搜索系统
World File Search SystemOWSG
将OWSG和量子资金与Qefid
在经典的加密术中，单向函数（OWF）被广泛认为是“最小假设”，但量子加密的情况就不太清楚。最近的作品提出了两个并发候选量子密码学中最小假设的候选者：单向状态发生器（OWSGS），假定具有有效的验证算法的硬搜索问题的存在，并且EFI对，并假定存在困难的区分问题。最近的两篇论文[Khurana和Tomer Stoc'24; Batra和Jain focs'24]表明OWSG表示EFI对，但反向方向保持开放。在这项工作中，我们提供了有力的证据，表明相反的方向不存在：我们表明存在量子统一的甲骨文，而efi对存在，但OWSG不存在。实际上，我们显示了一个稍强的陈述，该语句也适用于输出经典位（QEFID对）的EFI对。因此，我们通过Oracle，QEFID对和单向拼图与OWSG和其他几个MicroCrypt原始词分开，包括有效可验证的单向拼图和不可消除的状态生成器。特别是解决了[Chung，Goldin和Gray Crypto'24]中留下的问题。使用类似的技术，我们还建立了一个完全黑框的分离（比私钥量子货币方案和QEFID对之间的较弱的分离（比Oracle分离略弱）。我们工作的一种概念含义是，有效的验证算法的存在可能会导致量子密码学中质性更强的原始素。
量子密码学中的单向性 - 滴
单向函数的存在是经典cryp-图表中最基本的假设之一。在量子世界中，有些证据表明，即使单向函数不存在，也可以存在一些加密原语[Kretschmer，TQC 2021; Morimae和Yamakawa，Crypto 2022； Ananth，Qian和Yuen，Crypto 2022]。因此，我们在量子密码学中存在以下重要的开放问题：量子密码学中最基本的假设是什么？In this direction, [Brakerski, Canetti, and Qian, ITCS 2023] recently defined a notion called EFI pairs, which are pairs of efficiently generatable states that are statistically distinguishable but computationally indistinguishable, and showed its equivalence with some cryptographic primitives including commitments, oblivious transfer, and general multi-party computations.但是，他们的工作着重于决策类型的基础，并且不涵盖搜索类型的原始图，例如量子货币和数字签名。在本文中，我们研究了单向状态发生器（OWSG）的性质，这是Morimae和Yamakawa提出的单向函数的量子类似物。我们首先重新访问OWSG的定义，并通过允许混合输出状态进行概括。然后我们显示以下结果。
量子密码学中的单向性
单向函数的存在是经典加密策略中最基本的假设之一。在量子世界中，有些证据表明，即使单向函数不存在，也可以存在一些加密原语[Kretschmer，TQC 2021; Morimae和Yamakawa，Crypto 2022； Ananth，Qian和Yuen，Crypto 2022]。因此，我们在量子密码学中存在以下重要的开放问题：量子cryp- tography中最基本的假设是什么？In this direction, [Brakerski, Canetti, and Qian, ITCS 2023] recently defined a notion called EFI pairs, which are pairs of efficiently generatable states that are statistically distinguishable but com- putationally indistinguishable, and showed its equivalence with some cryptographic primitives including commitments, oblivious transfer, and general multi-party computations.但是，他们的工作着重于决策类型的基础，并且不涵盖搜索类型的原语，例如量子货币和数字签名。在本文中，我们研究了单向状态发生器（OWSG）的性质，这是Morimae和Yamakawa提出的单向函数的量子类似物。我们首先重新审视OWSG的定义，并通过允许混合的输出状态概括它。然后我们显示以下结果。
量子不可预测性 - 密码学电子印刷档案
不可预测函数 (UPF) 在经典密码学中起着重要作用，包括消息认证码 (MAC) 和数字签名。在本文中，我们介绍了 UPF 的量子类似物，我们称之为不可预测状态生成器 (UPSG)。UPSG 由伪随机函数类状态生成器 (PRFS) 隐含，伪随机函数类状态生成器是伪随机函数 (PRF) 的量子类似物，因此即使单向函数不存在，UPSG 也可能存在，类似于其他最近引入的原语，如伪随机状态生成器 (PRSG)、单向状态生成器 (OWSG) 和 EFI。在经典密码学中，UPF 等同于 PRF，但在量子情况下，等价性尚不清楚，UPSG 可能比 PRFS 弱。尽管如此，我们证明所有已知的 PRFS 应用也可以通过 UPSG 实现。它们包括 IND-CPA 安全密钥加密和具有不可克隆标签的 EUF-CMA 安全 MAC。我们的研究结果表明，对于许多应用来说，量子不可预测性而不是量子伪随机性就足够了。
论量子密码学与经典通信的中心原语
最近的研究为密码学引入了“量子计算经典通信”（QCCC）（Chung 等人）。有证据表明，单向谜题（OWPuzz）是此设置（Khurana 和 Tomer）的自然中心密码原语。被视为中心的原语应具备若干特征。它应行为良好（在本文中，我们将其视为具有放大、组合器和通用构造）；它应由多种其他原语所暗示；并且它应等同于某些类有用的原语。我们提出了组合器、正确性和安全性放大，以及 OWPuzz 的通用构造。我们对安全性放大的证明使用了来自 OWPuzz 的新的、更清晰的 EFI 构造（与 Khurana 和 Tomer 的结果相比），该构造可推广到弱 OWPuzz，是本文中技术含量最高的部分。此前已知 OWPuzz 由其他感兴趣的原语所隐含，包括承诺、对称密钥加密、单向状态生成器（OWSG）以及伪随机状态（PRS）。然而，我们能够通过展示一般 OWPuzz 与受限类 OWPuzz（具有有效验证的原语，我们称之为 EV-OWPuzz）之间的黑盒分离来排除 OWPuzz 与许多这些原语的等价性。然后我们证明 EV-OWPuzz 也由大多数这些原语所隐含，这也将它们与 OWPuzz 区分开来。这种分离还将扩展 PRS 与高度压缩 PRS 区分开来，回答了 Ananth 等人的一个悬而未决的问题。
从元复杂性出发的量子密码学
在经典密码学中，单向函数 (OWF) 是最小假设，而最近的活跃研究表明，OWF 不一定是量子密码学中的最小假设。已经引入了几个新的原语，例如伪随机幺正 (PRU)、伪随机函数状状态生成器 (PRFSG)、伪随机状态生成器 (PRSG)、单向状态生成器 (OWSG)、单向谜题 (OWPuzzs) 和 EFI 对。它们被认为比 OWF 弱，但它们仍然意味着许多有用的应用，例如私钥量子货币方案、密钥加密、消息认证码、数字签名、承诺和多方计算。既然没有 OWF 的量子密码学的可能性已经打开，该领域最重要的目标是为它们提供具体的实例。例如，在经典密码学中，有许多基于具体硬度假设的 OWF 实例，例如离散对数的硬度或带误差学习。通用原语的研究是由具体实例的存在所证明的。另一方面，在量子密码学中，这些原语的所有已知构造都仅来自 OWF。因此，我们有以下重要的未解决的问题：它们是否有基于某些不意味着 OWF 的具体难度假设的实例？理想情况下，这些假设应该是在密码学以外的其他背景下研究的假设。在本文中，我们通过证明 GapK 问题的量子平均难度意味着 OWPuzzs 的存在，给出了该问题的候选答案。GapK 问题是一个承诺问题，用于确定给定的位串是否具有较小的 Kolmogorov 复杂度。其量子平均难度意味着一个实例是从量子多项式时间可采样分布中采样的，并且没有量子多项式时间算法可以高概率地解决该问题。据我们所知，这是第一次基于似乎不暗示 OWF 的具体难度假设构建“微密码”原语。此外，这些假设在密码学以外的其他背景下进行了研究，特别是在元复杂性领域。（注：在准备这份手稿期间，Khurana 和 Tomer [KT24b] 上传了一项并发工作。）
量子优势的密码学表征
量子计算优势是指存在一些对于量子计算来说很容易但对于经典计算来说很难的计算任务。无条件地展示量子优势超出了我们目前对复杂性理论的理解，因此需要一些计算假设。哪种复杂性假设对于量子优势是必要且充分的？在本文中，我们证明了当且仅当存在经典安全单向谜题 (OWPuzzs) 时，量子性低效验证者证明 (IV-PoQ) 才存在。据我们所知，这是第一次获得量子优势的完整密码学表征。IV-PoQ 是量子性证明 (PoQ) 的泛化，其中验证者在交互过程中是高效的，但之后可能会使用无限时间。IV-PoQ 捕获了以前研究过的各种类型的量子优势，例如基于采样的量子优势和基于搜索的优势。先前的研究 [Morimae and Yamakawa, Crypto 2024] 表明 IV-PoQ 可以从 OWF 构建，但从较弱的假设构建 IV-PoQ 仍未可行。我们的结果解决了这个悬而未决的问题，因为人们认为 OWPuzzs 比 OWFs 弱。OWPuzzs 是最基本的量子密码原语之一，它由许多比单向函数 (OWF) 弱的量子密码原语所暗示，例如伪随机幺正 (PRU)、伪随机状态生成器 (PRSG) 和单向状态生成器 (OWSG)。因此，IV-PoQ 与经典安全 OWPuzzs 之间的等价性强调，如果没有量子优势，那么这些基本密码原语就不存在。这种等价性还意味着量子优势是 OWPuzzs 应用的一个例子。除了承诺之外，以前没有 OWPuzzs 的应用。我们的结果表明，量子优势是 OWPuzzs 的另一个应用，它解决了 [Chung, Goldin, and Gray, Crypto 2024] 的悬而未决的问题。此外，它是 OWPuzzs 的第一个量子计算经典通信 (QCCC) 应用。为了展示主要结果，我们引入了几个新概念并展示了一些独立有趣的结果。特别是，我们引入了一个交互式（和平均情况）版本的采样问题，其中的任务是对两个量子多项式时间算法之间的经典交互获得的转录进行采样。我们表明交互式采样问题中的量子优势等同于 IV-PoQ 的存在，它被认为是 Aaronson 结果 [Aaronson，TCS 2014] 的交互式（和平均情况）版本，SampBQP ̸ = SampBPP ⇔ FBQP ̸ = FBPP 。最后，我们还引入了零知识 IV-PoQ 并研究了它们存在的充分必要条件。