谢天元^{1, 2},
李昊宇^{1, 2},
朱熠铭^{1, 2},
潘彦斌^1,,,
刘珍^{1, 2},
杨照民^{1, 2}
1.中国科学院数学与系统科学研究院数学机械化重点实验室 北京 100190
2.中国科学院大学数学科学学院 北京 100049
基金项目:国家自然科学基金(61572490)

详细信息

作者简介:谢天元：女，1992年生，博士，研究方向为格密码算法设计与分析
李昊宇：男，1990年生，博士，研究方向为格密码算法设计与分析
朱熠铭：男，1994年生，博士，研究方向为格算法、编码
潘彦斌：男，1982年生，副研究员，研究方向为格算法及格密码算法分析
刘珍：女，1994年生，博士，研究方向为格算法及格密码算法分析
杨照民：男，1995年生，硕士，研究方向为格算法、后斯诺登密码

通讯作者:潘彦斌　panyanbin@amss.ac.cn

中图分类号:TN918.1

计量

文章访问数:2262
HTML全文浏览量:1032
PDF下载量:110
被引次数:0

出版历程

收稿日期:2019-09-04
修回日期:2019-12-11
网络出版日期:2019-12-19
刊出日期:2020-02-19

FatSeal: An Efficient Lattice-based Signature Algorithm

Tianyuan XIE^{1, 2},
Haoyu LI^{1, 2},
Yiming ZHU^{1, 2},
Yanbin PAN^1,,,
Zhen LIU^{1, 2},
Zhaomin YANG^{1, 2}
1. KLMM, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China
2. School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China
Funds:The National Natural Science Foundation of China (61572490)


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



PDF全文下载地址:

https://jeit.ac.cn/article/exportPdf?id=97153838-c267-4867-995f-58df070d624f