机构名称：
¥ 1.0
在经典密码学中，单向函数 (OWF) 是最小假设，而最近的活跃研究表明，OWF 不一定是量子密码学中的最小假设。已经引入了几个新的原语，例如伪随机幺正 (PRU)、伪随机函数状状态生成器 (PRFSG)、伪随机状态生成器 (PRSG)、单向状态生成器 (OWSG)、单向谜题 (OWPuzzs) 和 EFI 对。它们被认为比 OWF 弱，但它们仍然意味着许多有用的应用，例如私钥量子货币方案、密钥加密、消息认证码、数字签名、承诺和多方计算。既然没有 OWF 的量子密码学的可能性已经打开，该领域最重要的目标是为它们提供具体的实例。例如，在经典密码学中，有许多基于具体硬度假设的 OWF 实例，例如离散对数的硬度或带误差学习。通用原语的研究是由具体实例的存在所证明的。另一方面，在量子密码学中，这些原语的所有已知构造都仅来自 OWF。因此，我们有以下重要的未解决的问题：它们是否有基于某些不意味着 OWF 的具体难度假设的实例？理想情况下，这些假设应该是在密码学以外的其他背景下研究的假设。在本文中，我们通过证明 GapK 问题的量子平均难度意味着 OWPuzzs 的存在，给出了该问题的候选答案。GapK 问题是一个承诺问题，用于确定给定的位串是否具有较小的 Kolmogorov 复杂度。其量子平均难度意味着一个实例是从量子多项式时间可采样分布中采样的，并且没有量子多项式时间算法可以高概率地解决该问题。据我们所知，这是第一次基于似乎不暗示 OWF 的具体难度假设构建“微密码”原语。此外，这些假设在密码学以外的其他背景下进行了研究，特别是在元复杂性领域。（注：在准备这份手稿期间，Khurana 和 Tomer [KT24b] 上传了一项并发工作。）
从元复杂性出发的量子密码学
主要关键词
相关文件推荐
