XiaoMi-AI文件搜索系统
World File Search SystemPRFS
在量子随机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压缩甲骨文技术的替代形式化，给出紧密的量子绑定，我们引入了一种新的证明技术，重点是量子查询记录的对称性。
伪随机量子态密码学
伪随机态由 Ji、Liu 和 Song (Crypto'18) 引入，是可高效计算的量子态，在计算上与 Haar 随机态无法区分。单向函数意味着伪随机态的存在，但 Kretschmer (TQC'20) 最近构建了一个 oracle，相对于该 oracle 不存在单向函数，但伪随机态仍然存在。受此启发，我们研究了基于伪随机态执行有趣的加密任务的有趣可能性。假设存在将 𝜆 位种子映射到 𝜔 (log 𝜆 ) 量子比特状态的伪随机态生成器，我们构建了 (a) 统计上具有约束力且计算上具有隐藏性的承诺和 (b) 伪一次性加密方案。(a) 的结果是，伪随机态足以在多数不诚实的情况下构建恶意安全的多方计算协议。我们的构造是通过一种称为伪随机函数类状态 (PRFS) 的新概念得出的，这是伪随机状态的泛化，与经典的伪随机函数概念相似。除了上述两种应用之外，我们相信我们的概念可以有效地取代许多其他加密应用中的伪随机函数。
量子密码分析对相关钥匙设置（完整版）的收缩Feistel结构和观察
当每个回合的键控f函数仅与圆形键K I相差，并且假设没有歧义，我们将简单地表示f i = f（i）k i（x）。在经典环境中，已经证明，2分支平衡的Feistel-F结构成为R≥3的安全伪随机排列（PRP），当F（1）k 1时，R≥4的安全强伪随机置换（SPRP）。。。，f（r）k r是安全的prfs和k 1，。。。，k r在Random [19] 8中独立和均匀地选择。然而，在量子设置中，kuwakado和morii表明，可以通过量子选择的plaintext攻击（QCPA）在多项式时间内区分3圆平衡的Feistel结构。也就是说，3轮平衡的Feistel结构不是量子伪随机置换（QPRP）。随后的几部作品扩展了Kuwakado和Morii的区别。例如，有些人已经对平衡的Feistel结构产生了量子键恢复攻击[9,13]，并显示了对广义Feistel结构的量子攻击[8,12,21]。此外，在[14]中的4轮平衡Feistel结构上构建了多项式QCCA区分剂。但是，到目前为止，很少有研究人员专注于Feistel结构的重要变体：Feistel结构9。
量子计算的简洁经典验证
我们为量子计算 (BQP) 构建了一个经典可验证的简洁交互式论证，其通信复杂度和验证器运行时间在 BQP 计算的运行时间内是多对数的（在安全参数中是多项式的）。我们的协议是安全的，假设不可区分混淆 (iO) 和带错学习 (LWE) 的后量子安全性。这是普通模型中量子计算的第一个简洁论证；先前的工作（Chia-Chung-Yamakawa，TCC '20）需要长公共参考字符串和非黑盒使用以随机预言机建模的哈希函数。在技术层面，我们重新审视了构建经典可验证量子计算的框架（Mahadev，FOCS '18）。我们为 Mahadev 的协议提供了一个独立的模块化安全性证明，我们认为这是独立的兴趣。我们的证明很容易推广到验证者的第一条消息（包含许多公钥）被压缩的场景。接下来，我们将压缩公钥的概念形式化；我们将对象视为受约束/可编程 PRF 的泛化，并基于不可区分性混淆对其进行实例化。最后，我们使用（足够可组合的）简洁的 NP 知识论证将上述协议编译成完全简洁的论证。使用我们的框架，我们实现了几个额外的结果，包括
量子计算的简洁经典验证
摘要。我们为量子计算 (BQP) 构建了一个经典可验证的简洁交互式论证，其通信复杂性和验证器运行时间在 BQP 计算的运行时间内是多对数的（在安全参数中是多项式的）。我们的协议是安全的，假设不可区分混淆 (iO) 和错误学习 (LWE) 的后量子安全性。这是第一个简洁的论证，适用于普通模型中的量子计算；先前的工作（Chia-Chung-Yamakawa，TCC '20）既需要较长的公共参考字符串，又需要非黑盒使用以随机预言机建模的哈希函数。在技术层面，我们重新审视了构建经典可验证量子计算的框架（Mahadev，FOCS '18）。我们为 Mahadev 的协议提供了一个独立的模块化安全性证明，我们认为这是有独立意义的。我们的证明很容易推广到验证者的第一条消息（包含许多公钥）被压缩的场景。接下来，我们将压缩公钥的概念形式化；我们将该对象视为受限/可编程 PRF 的泛化，并基于不可区分混淆对其进行实例化。最后，我们使用（足够可组合的）NP 简洁知识论证将上述协议编译成完全简洁的论证。使用我们的框架，我们获得了几个额外的结果，包括 - QMA 的简洁论证（给定见证的多个副本）， - 量子随机预言模型中 BQP（或 QMA）的简洁非交互式论证，以及 - 假设后量子 LWE（无 iO）的 BQP（或 QMA）的简洁批处理论证。
量子线性化攻击
摘要。最近的研究表明，量子周期查找可用于破解叠加查询模型中的许多流行构造（一些分组密码，如 Even-Mansour、多个 MAC 和 AE……）。到目前为止，所有被破解的构造都表现出强大的代数结构，这使得能够构造单个输入块的周期函数。恢复秘密周期可以恢复密钥，区分并破坏这些模式的机密性或真实性。在本文中，我们介绍了量子线性化攻击，这是一种使用 Simon 算法针对叠加查询模型中的 MAC 的新方法。具体来说，我们使用多个块的输入作为隐藏线性结构的函数的接口。恢复此结构可以执行伪造。我们还介绍了这种攻击的一些变体，这些变体使用其他量子算法，这些算法在量子对称密码分析中不太常见：Deutsch、Bernstein-Vazirani 和 Shor 的算法。据我们所知，这是这些算法首次用于量子伪造或密钥恢复攻击。我们的攻击破解了许多可并行化的 MAC，例如 LightMac、PMAC 以及具有（经典）超龄安全性（LightMAC+、PMAC+）或使用可调整分组密码（ZMAC）的众多变体。更一般地说，这表明构建可并行化的量子安全 PRF 可能是一项具有挑战性的任务。
量子线性化攻击 - 密码学EPRINT存档
摘要。最近的作品表明，量子周期可以用于打破许多流行的构造（某些块密码，例如偶数，多个Mac和AES。。。 ）在叠加查询模型中。到目前为止，所有破碎的结构都表现出强大的代数结构，使得能够定期发挥单个输入块的定期功能。恢复秘密时期允许恢复钥匙，区分，打破这些模式的确定性或真实性。在本文中，我们介绍了量子线性化攻击，这是一种使用Simon的算法来定位叠加查询模型中MAC的新方法。特别是，我们使用多个块的输入作为隐藏线性结构的函数的接口。恢复此结构允许执行伪造。我们还提出了使用其他量子算法的这种攻击的一些变体，这些算法在量子对称地crypt-分析中不太常见：Deutsch's，Bernstein-Vazirani和Shor's。据我们所知，这是这些算法第一次用于伪造或钥匙恢复攻击中。我们的攻击破坏了许多可行的MAC，例如LightMac，PMAC和许多具有（经典的）超越生物结合安全性（Lightmac+，PMAC+）或使用可调整的块密码（ZMAC）的变体。更普遍地，它表明，构建可行的量子安全性PRF可能是一项具有挑战性的任务。
量子线性化攻击
摘要。最近的作品表明，量子周期可以用于打破许多流行的构造（某些块密码，例如偶数，多个Mac和AES。。。 ）在叠加查询模型中。到目前为止，所有破碎的结构都表现出强大的代数结构，使得能够定期发挥单个输入块的定期功能。恢复秘密时期允许恢复钥匙，区分，打破这些模式的确定性或真实性。在本文中，我们介绍了量子线性化攻击，这是一种使用Simon的算法来定位叠加查询模型中MAC的新方法。特别是，我们使用多个块的输入作为隐藏线性结构的函数的接口。恢复此结构允许执行伪造。我们还提出了使用其他量子算法的这种攻击的一些变体，这些算法在量子对称地crypt-分析中不太常见：Deutsch's，Bernstein-Vazirani和Shor's。据我们所知，这是这些算法第一次用于伪造或钥匙恢复攻击中。我们的攻击破坏了许多可行的MAC，例如LightMac，PMAC和许多具有（经典的）超越生物结合安全性（Lightmac+，PMAC+）或使用可调整的块密码（ZMAC）的变体。更普遍地，它表明，构建可行的量子安全性PRF可能是一项具有挑战性的任务。
OPA：单个客户端的单发私人聚合...
我们的工作最大程度地减少了安全计算中的互动，从而解决了沟通的高昂成本，尤其是与许多客户。我们介绍了单次私人聚合OPA，使客户只能在单服务器设置中进行每个聚合评估一次。这简化了辍学和动态参与，与Bonawitz等人等多轮协议形成鲜明对比。（CCS'17）（以及随后的作品），并避免了类似于Yoso的复杂委员会选择。OPA的沟通行为紧密地模仿每个客户群只会说话一次的学习。OPA建立在LWR，LWE，班级组和DCR上，可确保所有客户的单轮通信，同时还可以在客户数量中实现次线性开销，从而使其渐近且实用。我们通过中止和投入验证实现恶意安全，以防止中毒攻击，这在联邦学习中尤其重要，在这种学习中，对手试图操纵梯度以降低模型性能或引入偏见。我们从（阈值）密钥同型PRF和（2）的种子同源性PRG和秘密共享的（2）建立了两种口味（1）。阈值关键同构PRF解决了以前依赖于DDH和LWR的工作中观察到的缺点。（加密，2013年），将其标记为对我们工作的独立贡献。我们的其他贡献包括（阈值）键合型PRF和种子塑形PRG的新结构，这些构造是在LWE，DCR假设和其他未知顺序的类组下安全的结构。
量子伪随身和经典复杂性
伪随机性是复杂性理论和密码学中的关键概念，捕获了似乎随机与计算结合的对手的概念。最近的作品将计算伪随机性的理论扩展到了量子对象，特别关注类似于HAAR度量的量子状态和单一转换[JLS18，BS19，BFV20]。ji，liu和song [jls18]定义伪兰态（PRS）合奏，为量子状态的一个钥匙家族{| ϕ k⟩}k∈{0，1}κ，从集合中的状态可以在κ中产生。从多项式的许多副本中，ϕ k⟩。他们还定义了一个伪和统一转换（PRU）的集合，就像一组有效实现的单一转换，这些变换在计算上与HAAR量度无法区分。这些定义可以分别视为伪元发生器（PRGS）和伪andom函数（PRFS）的量子类似物。然后，作者提出了假设存在量子安全单向功能的PRSS的结构，并且还为他们猜想的PRU提供了候选PRUS的结构。已知伪随机状态和统一的几种应用。PRS和PRS在量子算法中很有用：在需要与HAAR度量近似的计算应用中，PRS和PRU可能比T -deSigns更有效，这些设计与HAAR度量相似的信息理论近似与T -Chise Indepen -dent -dent的功能相似。1此外，可以使用PRS和PRU（包括量子货币计划，量子承诺，安全的多方交流，一次性的数字签名，某些形式的对称对称性键加密等[JLS18，AQY22，AQY22，MY22B，BCQ23，My223，My23，My233）来实例化多种加密原始。最后，Bouland，Fe Q e Qulan和Vazirani [BFV20]在ADS/CFT对应关系中与所谓的“蠕虫孔生长悖论”之间建立了基本联系。