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

Improvements of Randomness Leakage Attacks Against Lattice-based Fiat-Shamir Signatures

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

Lattice-based Fiat-Shamir signature is an important kind of post quantum signatures,where Dilithium has been standardized by NIST.Liu et al.proposed that,when the randomness corresponding to the signature leaks one bit,the attack can be transformed into the ILWE problem which can be solved in polynomial time by Bootle et al.,and the least square method is used for recovering the secret key.Although the time complexity of the attack is polynomial,there are still many shortcomings such as a large number of signatures required,complex analysis procedure and being unable to attack the most efficient BLISS scheme in this type of signatures.This paper presents three improvements to the randomness leakage attack of lattice-based Fiat-Shamir signatures.Firstly,the search space of the private key is reduced by guessing bits after using the least squares method with less signatures,compared with Liu et al.’s scheme.Secondly,a new method of ILWE with ring structure proposed by Ye et al.is theoretically analyzed and experimentally verified.This method is effective when estimating the required number of signatures,and the computational efficiency is visibly improved at the cost of slightly increasing the required signatures.Finally,this paper extends the partial randomness leakage attack by Liu et al.to BLISS,which confirms that in all lattice-based Fiat-Shamir signatures,the randomness should be adequately protected to prevent possible randomness leakage attacks.