摘要。数字签名是各种协议中提供完整性和真实性的基本构建块。量子计算的发展引发了人们对传统签名方案所提供的安全保障的担忧。CRYSTALS-Dilithium 是一种基于格密码学的高效后量子数字签名方案,已被美国国家标准与技术研究所选为标准化的主要算法。在这项工作中,我们提出了 Dilithium 的高吞吐量 GPU 实现。对于单个操作,我们采用一系列计算和内存优化来克服顺序约束、减少内存使用和 IO 延迟、解决银行冲突并缓解管道停顿。这为每个操作带来了高且平衡的计算吞吐量和内存吞吐量。在并发任务处理方面,我们利用任务级批处理来充分利用并行性并实现内存池机制以实现快速内存访问。我们提出了一种动态任务调度机制来提高多处理器占用率并显着缩短执行时间。此外,我们采用异步计算并启动多个流来隐藏数据传输延迟,并最大限度地发挥 CPU 和 GPU 的计算能力。在所有三个安全级别中,我们的 GPU 实现在商用和服务器级 GPU 上实现了超过 160 倍的签名加速和超过 80 倍的验证加速。这为每个任务实现了微秒级的摊销执行时间,提供了一种适用于实际系统中各种应用的高吞吐量和抗量子解决方案。
摘要。当我们进入2024年,量子后加密算法Dilithium是从国家标准和技术研究所后的量词后加密术竞争中出现的,现已达到部署阶段。本文重点介绍了二锂的实际安全性。我们在STM32F4平台上对Dilithium2进行了实际攻击。我们的结果表明,可以在五分钟内仅使用两个签名执行攻击,一个签名提供了60%的概率,可以在一小时内恢复私钥。具体来说,我们分析了多项式添加z = y + cs 1。攻击分为两个阶段:最初应用侧通道分析以恢复Y或CS 1的值,然后求解错误的CS 1方程式系统。我们使用基于线性回归的概要攻击介绍Y恢复Y,利用添加大量和小数的数学特性,仅需要一个迹线才能达到40%的成功率。相比之下,基于CNN的模板攻击,经过200个签名的泄漏训练,使CS 1从单个轨迹中恢复,成功率为74%。此外,通过利用约束z = y + cs 1,y和cs 1的组合泄漏将CS 1回收的成功率提高到92%。另外,我们提出了一个基于约束优化的残差分析,以解决方程式CS 1 = b误差。此方法可以独立发挥作用,也可以作为预处理步骤,结合信念传播或整数线性编程。实验结果表明,该方法在公式集中的正确性率达到95%,可以在短短五秒钟内直接恢复私钥S 1,成功率为83%。即使正确的性率低至5%,该方法仍然可以使用约200个签名生成的方程式在5分钟内恢复私钥S 1。
在量子计算硬件的最新进展之后,国家标准技术研究所(NIST)是标准化的加密协议,这些协议可抵抗量子对手的攻击。NIST选择的主要数字签名方案是晶体-Dilithium。该方案的硬度基于三个计算问题的硬度:模块学习错误(MLWE),模块短整数解决方案(MSIS)和自助图。mlwe和msis经过了很好的研究,被广泛认为是安全的。然而,自我攻击是新颖的,尽管在经典上与MSI一样坚硬,但其量子硬度尚不清楚。在本文中,我们通过减少量子随机Oracle模型(QROM)中的MLWE来提供自我攻击性硬度的第一个证明。我们的证明使用了最近开发的量子重编程和倒带技术。我们方法的一个核心部分是证明了来自MSIS问题的某些哈希函数正在崩溃。从这种方法中,我们在适当的参数设置下得出了一个新的安全性证明。与Kiltz,Lyubashevsky和Schaffner(Eurocrypt 2018)的先前工作相比,它为DiLithium变体提供了唯一的其他严格安全证明,我们的证明具有适用于条件Q = 1 mod 2 N的优势,其中Q表示模量和n的模量和n的尺寸。此条件是原始二硫族提案的一部分,对于该计划的有效实施至关重要。9×和1。分别比Kiltz等人提出的分别大。我们在条件q = 1 mod 2 n下为二氨石提供了新的安全参数集,发现我们的公共密钥大小和签名大小约为2。在同一安全级别。