XiaoMi-AI文件搜索系统
World File Search SystemOWPuzzs
量子优势的加密表征
量子计算优势是指容易用于量子计算的计算任务的存在，但对于经典的计算很难。无条件显示量子优势超出了我们当前对复杂性理论的理解，因此需要一些计算假设。哪种复杂性假设是必要的，并且足以满足量子优势？在本文中，我们证明存在量子性（iv-poq）时，并且仅当存在经典的单向拼图（Owpuzzs）时，就存在量子性的量化证明（IV-POQ）。据我们所知，这是第一次获得量子优势的完全加密表征。iv-poq是量子性证明（POQ）的概括，其中verifier在交互期间有效，但随后可能会使用无限的时间。IV-POQ捕获先前研究的各种类型的量子优势，例如基于采样的量子优势和基于搜索的量子优势。 先前的工作[Morimae和Yamakawa，Crypto 2024]表明，可以从OWFS构建IV-POQ，但是从较弱的假设中构建IV-POQ的结构是敞开的。 我们的结果解决了开放问题，因为据信owpuzzs比OWF弱。 owpuzzs是许多量子加密原语所暗示的最基本的量子加密原语之一，而不是单向函数（OWFS），例如伪和单位单位（PRUS），pseudorandom andom state state nate state Intate Generators（PRSGS）和单向状态生成器（单向状态生成器（OWN）。 因此，IV-POQ与经典的Owpuzzs之间的等效性强调，如果没有量子优势，那么这些基本的加密原始原始物将不存在。IV-POQ捕获先前研究的各种类型的量子优势，例如基于采样的量子优势和基于搜索的量子优势。先前的工作[Morimae和Yamakawa，Crypto 2024]表明，可以从OWFS构建IV-POQ，但是从较弱的假设中构建IV-POQ的结构是敞开的。我们的结果解决了开放问题，因为据信owpuzzs比OWF弱。owpuzzs是许多量子加密原语所暗示的最基本的量子加密原语之一，而不是单向函数（OWFS），例如伪和单位单位（PRUS），pseudorandom andom state state nate state Intate Generators（PRSGS）和单向状态生成器（单向状态生成器（OWN）。因此，IV-POQ与经典的Owpuzzs之间的等效性强调，如果没有量子优势，那么这些基本的加密原始原始物将不存在。等效性还意味着量子助理是Owpuzzs应用程序的一个示例。承诺以外，以前没有知道Owpuzzs的应用。我们的结果表明，量子优势是Owpuzzs的另一种应用，它解决了[Chung，Goldin和Gray，Crypto 2024]的开放问题。此外，它是Owpuzzs的第一个量子计算 - 经典交流（QCCC）。为了显示主要结果，我们介绍了几个新概念，并显示了一些将引起独立感兴趣的结果。尤其是我们引入了一个交互式（和平均值）版本的采样问题，其中该任务是通过两个量子脉络化的tompolynomial-timealgorithm之间的经典相互作用来采样转录本。我们表明，QuantumAdvantional的交互式抽样问题等同于IV-POQ的存在，IV-POQ被认为是Aaronson结果的交互式（和平均值）版本[Aaronson，TCS，TCS 2014]，SAMPBQP = SAMPBQP = SAMPBPP。最后，我们还引入了零知识的IV-POQ，并为其存在的研究足够和必要的条件。
量子优势的密码学表征
量子计算优势是指存在一些对于量子计算来说很容易但对于经典计算来说很难的计算任务。无条件地展示量子优势超出了我们目前对复杂性理论的理解，因此需要一些计算假设。哪种复杂性假设对于量子优势是必要且充分的？在本文中，我们证明了当且仅当存在经典安全单向谜题 (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 并研究了它们存在的充分必要条件。
量子加密和元复杂性
在经典密码学中，单向函数（OWFS）是最小的假设，而量子密码学中并非如此。引入了几种新的原语，例如伪兰顿单位（PRUS），伪andomfunction-likestate Generator（PRFSGS），PseudorandomState Generators（PRSGS），单向状态发电机（OWSGS），单向路线（OWNWAIGH），单向（Owpuzzs）（Owpuzzles）和EFAUZZS和EFAIRT。它们似乎比OWF弱，但仍然意味着许多有用的应用程序，例如私钥量子货币方案，秘密键加密，消息身份验证代码，数字签名，承诺和多方计算。现在，没有OWF的量子加密的可能性已经开放，该领域最重要的目标是建立它的基础。在本文中，我们第一次表征了具有元复杂性的量子加密原语。我们表明，当且仅当Gapk是弱量化的量子时，就存在单向拼图（Owpuzzs）。Gapk是一个有望的问题，可以决定给定的位字符串是否具有小的Kolmogorov复杂性。弱量化 - 平均强度意味着实例是从QPT可采样分布中采样的，对于任何QPT对手，其造成错误的可能性大于1 / poly。我们还表明，如果存在量子PRG，则GAPK是强烈的量子 - 平均水平。在这里，强烈的量化 - hardis是弱量化量的强度，其中对手犯错的概率大于1 /2 - 1 / poly。最后，我们表明，如果GAPK是弱经典的平均水平，那么就存在量子性（IV-POQ）的不可能证明。弱经典的平均雄硬与弱量子平均硬化相同，但对手是PPT。IV-POQ是捕获基于采样和基于搜索的量子优势的量子性证明（POQ）的概括，并且是Owpuzzs的重要应用。 这是量子优势基于元复杂性的第一个时间。 （注意：有两项并发作品，[KT24B，CGGH24]。）IV-POQ是捕获基于采样和基于搜索的量子优势的量子性证明（POQ）的概括，并且是Owpuzzs的重要应用。这是量子优势基于元复杂性的第一个时间。（注意：有两项并发作品，[KT24B，CGGH24]。）
从元复杂性出发的量子密码学
在经典密码学中，单向函数 (OWF) 是最小假设，而最近的活跃研究表明，OWF 不一定是量子密码学中的最小假设。已经引入了几个新的原语，例如伪随机幺正 (PRU)、伪随机函数状状态生成器 (PRFSG)、伪随机状态生成器 (PRSG)、单向状态生成器 (OWSG)、单向谜题 (OWPuzzs) 和 EFI 对。它们被认为比 OWF 弱，但它们仍然意味着许多有用的应用，例如私钥量子货币方案、密钥加密、消息认证码、数字签名、承诺和多方计算。既然没有 OWF 的量子密码学的可能性已经打开，该领域最重要的目标是为它们提供具体的实例。例如，在经典密码学中，有许多基于具体硬度假设的 OWF 实例，例如离散对数的硬度或带误差学习。通用原语的研究是由具体实例的存在所证明的。另一方面，在量子密码学中，这些原语的所有已知构造都仅来自 OWF。因此，我们有以下重要的未解决的问题：它们是否有基于某些不意味着 OWF 的具体难度假设的实例？理想情况下，这些假设应该是在密码学以外的其他背景下研究的假设。在本文中，我们通过证明 GapK 问题的量子平均难度意味着 OWPuzzs 的存在，给出了该问题的候选答案。GapK 问题是一个承诺问题，用于确定给定的位串是否具有较小的 Kolmogorov 复杂度。其量子平均难度意味着一个实例是从量子多项式时间可采样分布中采样的，并且没有量子多项式时间算法可以高概率地解决该问题。据我们所知，这是第一次基于似乎不暗示 OWF 的具体难度假设构建“微密码”原语。此外，这些假设在密码学以外的其他背景下进行了研究，特别是在元复杂性领域。（注：在准备这份手稿期间，Khurana 和 Tomer [KT24b] 上传了一项并发工作。）