XiaoMi-AI文件搜索系统
World File Search System随机函数
5轮Feistel方案和Benes方案的量子密码分析
有多种方法可以构建伪随机排列和伪随机函数。随机 Feistel 密码也称为 Luby–Rackoff 分组密码，是用于构建分组密码的对称结构。 Feistel 网络的优点是相同的结构可用于加密和解密，两者都包括以固定次数迭代运行一个称为“轮函数”的函数。从随机函数或随机排列构建伪随机排列研究最多的方法是 r 轮 Feistel 构造。Feistel 构造从实用角度来看很重要，因为它用于开发许多分组密码，如 DES [ 2 ]、3DES [ 2 ]。我们研究对 Feistel 方案的一般攻击，其中我们假设内部轮函数 f 1 , . . . , fr 是随机选择的。Feistel 方案的明文消息用 [ L, R ] 表示，代表左和右，应用 r 轮后的密文消息用 [ S, T ] 表示。Feistel 方案的一轮以 [ L, R ] 作为输入，输出 [ R, L ⊕ f ( R )]，其中 f 是 n 位到 n 位的秘密函数。Benes 方案是两个方案的组合，称为“蝴蝶”。它允许从 n 位到 n 位的随机函数构造一个 2 n 位到 2 n 位的伪随机函数。对于许多加密原语（例如散列和伪随机函数），将输出长度加倍是有用的，即使加倍变换不可逆。
量子随机函数的组合方法
伪随机函数 (PRF) 是现代密码学的基本组成部分之一。Goldreich、Goldwasser 和 Micali 在开创性著作 [ 13 ] 中引入了 PRF，回答了如何构建一个与随机函数难以区分的函数的问题。粗略地说，PRF 可以保证没有任何有效算法能够通过 oracle 访问这样的函数而将其与真正的随机函数区分开来。事实证明，PRF 是密码原语（如分组密码和消息认证码）设计中的宝贵工具，而且现在已成为一个很好理解的对象：继 [ 13 ] 基于树的构造之后，PRF 已从伪随机合成器 [ 19 ] 和直接从许多难题 [ 20 、 21 、 22 、 11 、 18 、 7 、 2 ] 构建而成。然而，当考虑更精细的量子设置时，对 PRF 硬度的研究仍处于起步阶段。在深入研究这一原语的细节之前，需要进行一些澄清，因为可以用两种方式定义 PRF 的量子安全性：
量子不可预测性 - 密码学电子印刷档案
不可预测函数 (UPF) 在经典密码学中起着重要作用，包括消息认证码 (MAC) 和数字签名。在本文中，我们介绍了 UPF 的量子类似物，我们称之为不可预测状态生成器 (UPSG)。UPSG 由伪随机函数类状态生成器 (PRFS) 隐含，伪随机函数类状态生成器是伪随机函数 (PRF) 的量子类似物，因此即使单向函数不存在，UPSG 也可能存在，类似于其他最近引入的原语，如伪随机状态生成器 (PRSG)、单向状态生成器 (OWSG) 和 EFI。在经典密码学中，UPF 等同于 PRF，但在量子情况下，等价性尚不清楚，UPSG 可能比 PRFS 弱。尽管如此，我们证明所有已知的 PRFS 应用也可以通过 UPSG 实现。它们包括 IND-CPA 安全密钥加密和具有不可克隆标签的 EUF-CMA 安全 MAC。我们的研究结果表明，对于许多应用来说，量子不可预测性而不是量子伪随机性就足够了。
5轮Feistel方案和Benes方案的量子密码分析
存在多种构造伪随机排列和伪随机函数的方法。随机 Feistel 密码也称为 Luby-Rackoff 分组密码，是用于构造分组密码的对称结构。Feistel 网络的好处是相同的结构可用于加密和解密，并且两者都包括以固定次数迭代运行一个称为“轮函数”的函数。从随机函数或随机排列构建伪随机排列研究最多的方法是 r 轮 Feistel 构造。Feistel 构造从实用角度来看很重要，因为它被用于开发许多分组密码，如 DES [ 2 ]、3DES [ 2 ] 和 Simon [ 7 ]。我们研究了对 Feistel 方案的一般攻击，其中我们假设内部轮函数 f 1 , ... , fr 是随机选择的。 Feistel 方案的明文消息用 [ L, R ] 表示，代表左和右，经过 r 轮后的密文消息用 [ S, T ] 表示。Feistel 方案的第一轮以 [ L, R ] 作为输入，输出 [ R, L ⊕ f ( R )]，其中 fa 是 n 位到 n 位的秘密函数。Benes 方案是两个称为“蝴蝶”方案的组合。它允许从 n 位到 n 位的随机函数构造一个 2 n 位到 2 n 位的伪随机函数。对于许多密码原语（例如散列和伪随机函数），将输出长度加倍是有用的，即使加倍变换不可逆。Benes 方案的明文消息用 [ L, R ] 表示，代表左和右，密文消息用 [ S, T ] 表示。
伪随机量子态密码学
伪随机态由 Ji、Liu 和 Song (Crypto'18) 引入，是可高效计算的量子态，在计算上与 Haar 随机态无法区分。单向函数意味着伪随机态的存在，但 Kretschmer (TQC'20) 最近构建了一个 oracle，相对于该 oracle 不存在单向函数，但伪随机态仍然存在。受此启发，我们研究了基于伪随机态执行有趣的加密任务的有趣可能性。假设存在将 𝜆 位种子映射到 𝜔 (log 𝜆 ) 量子比特状态的伪随机态生成器，我们构建了 (a) 统计上具有约束力且计算上具有隐藏性的承诺和 (b) 伪一次性加密方案。(a) 的结果是，伪随机态足以在多数不诚实的情况下构建恶意安全的多方计算协议。我们的构造是通过一种称为伪随机函数类状态 (PRFS) 的新概念得出的，这是伪随机状态的泛化，与经典的伪随机函数概念相似。除了上述两种应用之外，我们相信我们的概念可以有效地取代许多其他加密应用中的伪随机函数。
在量子随机Oracle模型中HMAC和NMAC的紧密量子安全性
摘要。HMAC和NMAC是将Merkle-DamgLARD HASH函数转换为消息Au-thentication代码（MACS）或伪随机函数（PRFS）的最基本和重要结构。在Crypto 2017上，Song和Yun在标准假设下表明HMAC和NMAC是量子伪函数（QPRF），即潜在的压缩函数是QPRF。当HMAC和NMAC的输出长度为n位时，他们的证明可确保安全性高达O（2 N/ 5）或O（2 N/ 8）量子查询。但是，可证明的安全性约束与使用O（2 N/ 3）量子查询的简单区分攻击之间存在差距。本文解决了缩小差距的问题。我们表明，将HMAC或NMAC与随机函数区分开的量子查询数的紧密结合是量子随机甲骨文模型中的θ（2 n/ 3），其中压缩函数被建模为量子随机甲壳。基于Zhandry压缩甲骨文技术的替代形式化，给出紧密的量子绑定，我们引入了一种新的证明技术，重点是量子查询记录的对称性。
在多方计算中将随机性应用于安全性和隐私性
摘要 - 安全的多方计算（MPC）是分布式计算方法之一，它在其中计算一个函数，超过一个以上的一方共同给出的输入，并将这些输入与该过程中涉及的各方保持私密。秘密共享中的随机化导致MPC是对隐私增强的要求；但是，大多数可用的MPC模型都使用共享和组合值的信任假设。因此，忽略了秘密共享和MPC模块中的随机化。因此，可用的MPC模型容易出现信息泄漏问题，其中模型可以揭示共享秘密的部分值。在本文中，我们提出了使用随机函数发生器作为MPC原始的第一个模型。更具体地说，我们分析了对称随机函数生成器（SRFG）的先前开发，以提供信息理论安全性，如果系统安全地与无限计算资源和时间的对手有关，则该系统被认为具有无条件安全性。此外，我们应用SRFG来消除一般MPC模型中信息泄漏的问题。通过一组实验，我们表明SRFG是一个函数生成器，可以生成具有N/ 2-私有化到N-私有规范的组合函数（逻辑门的组合）。作为MPC的主要目标是对投入的隐私保护，我们分析了SRFG属性在秘密共享和MPC中的适用性，并观察到SRFG有资格成为MPC开发中的加密原始性。我们观察到，我们基于SRFG的MPC在吞吐量方面要好得多30％，并且还显示100％的隐私达到。我们还通过其他基于随机性生成的MPC框架来衡量我们提出的基于SRFG的MPC框架的性能，并使用最先进的模型分析了比较属性。
基于游戏的密码学
在此AFP条目中，我们展示了如何使用Crypthol Framework从文献中正式证明基于游戏的加密安全性概念，并正式证明了一些加密构造。除其他外，我们将随机甲骨文的概念，伪随机函数，不可预测的函数以及在所选的明文和/或ciphertext攻击下呈现不佳的加密方案。我们证明了随机排列/随机功能开关引理，Elgamal和Hashed Elgamal公共密钥加密方案的安全性以及具有伪随机函数的几种构造的正确性和安全性。我们的证据遵循Shoup [19]和Bellare和Rogaway [4]提倡的游戏风格，从中取了大多数示例。我们概括了他们的一些结果，以便可以在其他证据中重复使用。多亏了克里普托与伊莎贝尔的参数内部的集成，使用代表独立性理论可以很容易地为许多简单的啤酒花构成。
量子密钥可撤销双 Regev 加密，重新审视
量子信息可用于实现经典加密无法实现的新型加密原语。Ananth、Poremba、Vaikuntanathan (TCC 2023) 最近的一项工作重点是使用量子信息为 Gentry、Peikert、Vaikuntanathan (STOC 2008) 引入的双 Regev 加密方案配备密钥撤销功能。他们进一步表明，密钥可撤销双 Regev 方案意味着存在完全同态加密和伪随机函数，它们都配备了密钥撤销功能。不幸的是，他们只能根据新的猜想证明其方案的安全性，而没有解决基于经过充分研究的假设来确定密钥可撤销双 Regev 加密安全性的问题。在这项工作中，我们解决了这个悬而未决的问题。假设具有误差的多项式学习难度（超过亚指数模数），我们证明密钥可撤销双 Regev 加密是安全的。因此，我们首次获得以下结果：