基于格Fiat-Shamir签名随机数泄漏攻击的若干改进

摘要：

基于格的Fiat-Shamir签名是一类重要的后量子签名方案,其中Dilithium方案已成为NIST待标准化的签名算法.Liu等人首次提出,基于格的Fiat-Shamir签名对应的随机数只泄漏一比特时,可以将攻击转化为Bootle等人证明可多项式时间求解的ILWE问题,并采用最小二乘法进行恢复私钥.虽然该攻击的时间复杂度是多项式级别的,但是依然存在着所需签名较多、分析方法复杂以及无法攻击目前该类签名中效率最高的BLISS方案等不足.本文提出了基于格的Fiat-Shamir签名随机数泄漏攻击三方面的改进.利用猜测比特的方式降低私钥的搜索空间,降低攻击所需签名数;对Ye等人提出的带有环结构的ILWE的新的求解方法进行了理论分析和实验验证.该方法更容易估计所需签名数,并且以略微增加所需签名数为代价换来了计算效率的提升;首次将Liu等人提出的攻击方法推广至BLISS方案中,进一步证实了目前所有的基于格的Fiat-Shamir签名中,随机数都需要做好足够的防护,以防止可能的随机数泄漏攻击.

关键词：格签名、统计分析、随机数泄漏攻击

所属期刊栏目：9

分类号：TP309.7(计算技术、计算机技术)

在线出版日期：2023-02-15（万方平台首次上网日期，不代表论文的发表时间）

页数：共14页

页码：1039-1052