FatSeal:一种基于格的高效签名算法

FatSeal: An Efficient Lattice-based Signature Algorithm

当前基于格设计的能够抵抗量子计算机攻击的签名方案是基于数论难题的传统签名方案的热门候选替代。通过Fiat-Shamir变换以及拒绝采样技术构造格签名是一种重要方法,共有5个格签名方案提交到美国国家标准与技术局的后量子算法项目中,基于Fiat-Shamir变换进行设计的有两个方案。其中Dilithium是基于模错误学习(MLWE)问题构造的Fiat Shamir签名,它的一个特性是在签名算法中使用了高效简洁的均匀采样。Dilithium签名方案构造在一般格上,为了获得更紧凑的公钥尺寸,Dilithium对公钥进行了压缩。另一方面,NTRU格上的密码方案比一般格上的密码方案在效率和参数尺寸上有更大的优势,该文给出了Dilithium签名在NTRU格上的一个高效变种方案,在继承Dilithium简洁设计的基础上,综合了NTRU和拒绝采样的技术优势而无需额外的压缩处理,进一步提升了基于格的Fiat-Shamir签名的效率。

The lattice-based signature schemes are promising quantum-resistant replacements for classical signature schemes based on number theoretical hard problems. An important approach to construct lattice-based signature is utilizing the Fiat-Shamir transform and rejection sampling techniques. There are two Fiat-Shamir signatures among five lattice signature schemes submitted to the post-quantum project initiated by National Institute of Standards and Technology. One of them is called Dilithium, which is based on Module-Learning-With-Errors(MLWE) problem, it features on its simple design in the signing algorithm by using uniform sampling. The Dilithium is built on the generic lattices, to make the size of public key more compact,Dilithium adopts compression technique. On the other hand, schemes using NTRU lattices outperform schemes using generic lattices in efficiency and parameter sizes. This paper devotes to designing an efficient NTRU variant of Dilithium, by combining the advantage of NTRU and uniform rejection sampling, this scheme enjoys a concise structure and gains performance improvement over other lattice-based Fiat-Shamir signature without using extra compression techniques.