XiaoMi-AI文件搜索系统
World File Search SystemMicroCrypt
构建和分离量子伪随机
众所周知，对于几乎所有现代经典和量子加密任务来说，计算假设都是必需的。对经典隐身性的最小假设是单向函数（OWF）的存在。该假设已知与许多其他加密应用的存在相当，例如伪数编号生成，伪界函数，数字签名，对称键加密和承诺（请参阅，例如，参见[GOL01，GOL04]）。量子设置呈现出截然不同的图片：已知各种量子原始图，足以构建密码学，但可能比单向功能弱。最近，Tomoyuki Morimae创造了Microcrypt一词，是Impagliazzo的五个世界[IMP95]的补充，是指此类量子原始素（及其加密应用）2。MicroCrypt的租户之一是伪兰态（PRS），首先由JI，Liu和Song [JLS18]引入。这是一个有效生成的量子状态{| ϕk⟩}k∈{0，1} n，因此很难在多个副本上区分（a）|的多个副本。 ϕ k⟩从家族中采样，（b）均匀（HAAR）随机量子状态。ji，liu和Song还提供了OWF的Black Box结构。许多加密应用是基于MicroCrypt假设而知道的。也许更令人惊讶的是，MicroCrypt还包含一些隐藏狂的任务，即安全的多方计算[MY22B，BCKM21，GLSV21]和Quantum Publicum public Keys [BGHD + 23]。Subsequent to [ JLS18 ], many other tenants of Microcrypt have been introduced, such as pseudorandom function-like states ( PRFS ) [ AGQY22 ], efficiently samplable statistically far-but-computationally-indistinguishable pairs of (mixed) quan- tum states ( EFI pairs) [ Yan22 , BCQ23 ], one-way state generators [ MY22b ]和伪兰态具有破坏证明[BBSS23]。到目前为止，所有主要微型晶体3的变体已被证明在微晶中，包括对称 - 关键加密，承诺（最近，也承诺对量子状态[GJMZ23]），PRGS，PRFS，PRFS，GALBLED CICUCTITS，GALBLED CICUCTITS，MESSAGE AUTHERTICATION代码和数字信号。引起惊喜的关键因素是不可思议的和鲁迪奇的单向功能（微型级）和公钥加密4和遗忘转移（Cryptomania）[IR89]之间的分离。新的结构规定了古典不可能，因为它们涉及量子状态，例如承诺和多方计算取决于量子通信，加密方案具有量子密文。这些量子原语的证据比微小的弱点弱来自Kretschmer的PRS和OWF S [KRE21]的量子甲骨文分离。分离的甲骨文由一个族{u n}n∈N组成，其中u n是指数列表的许多HAAR随机n -qubit nimaries {u k}k∈{0，1} n。相对于此甲骨文，有一个简单的prs结构：k∈{0，1} n，让| ϕ k⟩：= u k | 0 n⟩。请注意，如果我们只考虑UNINERIES U K在标准基础上的行动，即一组状态U K | x⟩对于x∈{0，1} n，因此，对于每个n，可以将kretschmer的甲骨文视为提供2 2 2 n“本质上是Haar随机”状态5。在另一项作品中，Bouland，Fefferman和Vazirani [BFV19]显示了6 a prs构造相对于一个家庭{u n}n∈N，其中u n =（u，u - - 1）对于HAAR Random
将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分离略弱）。我们工作的一种概念含义是，有效的验证算法的存在可能会导致量子密码学中质性更强的原始素。
从元复杂性出发的量子密码学
在经典密码学中，单向函数 (OWF) 是最小假设，而最近的活跃研究表明，OWF 不一定是量子密码学中的最小假设。已经引入了几个新的原语，例如伪随机幺正 (PRU)、伪随机函数状状态生成器 (PRFSG)、伪随机状态生成器 (PRSG)、单向状态生成器 (OWSG)、单向谜题 (OWPuzzs) 和 EFI 对。它们被认为比 OWF 弱，但它们仍然意味着许多有用的应用，例如私钥量子货币方案、密钥加密、消息认证码、数字签名、承诺和多方计算。既然没有 OWF 的量子密码学的可能性已经打开，该领域最重要的目标是为它们提供具体的实例。例如，在经典密码学中，有许多基于具体硬度假设的 OWF 实例，例如离散对数的硬度或带误差学习。通用原语的研究是由具体实例的存在所证明的。另一方面，在量子密码学中，这些原语的所有已知构造都仅来自 OWF。因此，我们有以下重要的未解决的问题：它们是否有基于某些不意味着 OWF 的具体难度假设的实例？理想情况下，这些假设应该是在密码学以外的其他背景下研究的假设。在本文中，我们通过证明 GapK 问题的量子平均难度意味着 OWPuzzs 的存在，给出了该问题的候选答案。GapK 问题是一个承诺问题，用于确定给定的位串是否具有较小的 Kolmogorov 复杂度。其量子平均难度意味着一个实例是从量子多项式时间可采样分布中采样的，并且没有量子多项式时间算法可以高概率地解决该问题。据我们所知，这是第一次基于似乎不暗示 OWF 的具体难度假设构建“微密码”原语。此外，这些假设在密码学以外的其他背景下进行了研究，特别是在元复杂性领域。（注：在准备这份手稿期间，Khurana 和 Tomer [KT24b] 上传了一项并发工作。）