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

谢天元; 李昊宇; 朱熠铭; 潘彦斌; 刘珍; 杨照民

doi:10.11999/JEIT190678

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

doi: 10.11999/JEIT190678

谢天元^{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
计量
- 文章访问数: 3990
- HTML全文浏览量: 1886
- PDF下载量: 206
- 被引次数: 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.
- Digital signature /
- Lattice /
- Fiat-Shamir transform /
- Post-quantum /
- Rejection sampling

HTML全文

表 1 FatSeal密钥生成算法

算法1 FatSeal.KeyGen()
输入：$n,q$
输出：公钥$h$，私钥$(f,g)$
(1) $f,g \leftarrow T(d{\rm{ + 1}},d)$
(2) 如果$f$在${R_q}$中不可逆，跳转(1)
(3) 计算$h = (g + \alpha ){f^{ - 1}}$
(4) 输出$pk = h$, $sk = (f,g)$

下载: 导出CSV

表 2 FatSeal签名算法

算法2 FatSeal.Sign()
输入：消息$M$，公钥$h$，私钥$(f,g)$
输出：消息$M$的签名$(z,c)$
(1) $r \leftarrow {{\mathbb Z}_\alpha }[x]/({x^n} + 1)$
(2) 计算$w = hr{od ^\alpha }q$
(3) 若$w$的某分量等于$q - 1 - \alpha /2$，跳转(1)
(4) 计算$c = H(M,{\rm{quo}}(w))$
(5) 计算$z = r + cf$
(6) 若${\left\\| {cg} \right\\|_\infty } \le \gamma ,\;{\left\\| {cf} \right\\|_\infty } \le \gamma ,\;{\left\\| {cg + {\rm{rem}}(w)} \right\\|_\infty } \le \alpha /2 - \gamma , $　　　${\left\\| z \right\\|_\infty } < \alpha /2 - \gamma $，输出$(z,c)$
(7) 否则，跳转步骤(1)

下载: 导出CSV

表 3 FatSeal验签算法

算法3 FatSeal.Verify()
输入：消息$M$，公钥$h$，签名$(z,c)$
输出：验证成功输出1，否则输出0
(1) 如果${\left\\| z \right\\|_\infty } \ge \alpha /2 - \gamma $或${w{'} } = hz - \alpha c{od ^\alpha }q$的某个分　　　　量等于$q - 1 - \alpha /2$，输出0
(2) 否则
(3) 计算${c{'} } = H(M,{\rm{quo} }({w{'} }))$
(4) 如果${c{'} } = c$，输出1
(5) 否则，输出0

下载: 导出CSV

表 4 FatSeal签名方案的参数选取及迭代概率估计

$n$	$T(d + 1,d)$	$q$	$\omega $	$t$	$\alpha $	$\gamma $	迭代概率(%)
1024	T(257, 256)	286712	106	44	35840	20	10.2
2048	T(413, 412)	724993	287	87	90624	24	11.4

下载: 导出CSV

表 5 FatSeal签名128 bit和256 bit安全强度下的参数大小(Byte)

体制	公钥长度	私钥长度	签名长度
FatSeal-1024	2321	385	2048
FatSeal-2048	4984	719	4352

下载: 导出CSV

表 6 qTESLA签名128 bit和256 bit安全强度下的参数大小(Byte)

体制	公钥长度	私钥长度	签名长度
qTESLA-Ⅱ	2336	1600	2144
qTESLA-Ⅴ	5024	3520	4640

下载: 导出CSV

表 7 混合攻击下的FatSeal比特安全性

模型	体制	$b$	$N$	${r_1}$	比特安全性
classical	FatSeal-1024	510	1770	91	150
quantum	FatSeal-1024	522	1799	75	139
plausible	FatSeal-1024	549	1865	40	115
classical	FatSeal-2048	1130	3440	240	331
quantum	FatSeal-2048	1157	3503	207	307
plausible	FatSeal-2048	1219	3646	132	253

下载: 导出CSV

表 8 NewHope攻击模型下的比特安全性

体制	攻击模型	m	b	classical	quantum	plausible
FatSeal-1024	primal	874	503	147	133	104
FatSeal-1024	dual	862	502	146	133	104
FatSeal-2048	primal	1671	1076	314	285	223
FatSeal-2048	dual	1697	1072	313	284	222

下载: 导出CSV

表 9 SIS攻击下的比特安全性

模型	体制	$b$	$w$	比特安全性
classical	FatSeal-1024	577	2048	181
quantum	FatSeal-1024	577	2048	166
plausible	FatSeal-1024	577	2048	132
classical	FatSeal-2048	1276	4039	379
quantum	FatSeal-2048	1278	4041	344
plausible	FatSeal-2048	1284	4049	270

下载: 导出CSV

参考文献(24)

GOLDREICH O, GOLDWASSER S, and HALEVI S. Public-key cryptosystems from lattice reduction problems[C]. The 17th Annual International Cryptology Conference, Santa Barbara, USA, 1997: 112–131. doi: 10.1007/BFb0052231.

BABAI L. On Lovász’ lattice reduction and the nearest lattice point problem[J]. Combinatorica, 1986, 6(1): 1–13. doi: 10.1007/BF02579403

HOFFSTEIN J, PIPHER J, and SILVERMAN J H. NSS: An NTRU lattice-based signature scheme[C]. International Conference on the Theory and Application of Cryptographic Techniques, Innsbruck, Austria, 2001: 211–228. doi: 10.1007/3-540-44987-6.

NGUYEN P Q and REGEV O. Learning a parallelepiped: Cryptanalysis of GGH and NTRU signatures[C]. The 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, 2006: 271–288. doi: 10.1007/11761679_17.

GENTRY C, PEIKERT C, and VAIKUNTANATHAN V. Trapdoors for hard lattices and new cryptographic constructions[C]. The 40th Annual ACM Symposium on Theory of Computing, Victoria, 2008: 197–206. doi: 10.1145/1374376.1374407.

FOUQUE P A, HOFFSTEIN J, KIRCHNER P, et al. Fast-fourier lattice-based compact signatures over NTRU[EB/OL]. https://falcon-sign.info/, 2019.

LYUBASHEVSKY V. Fiat-shamir with aborts: Applications to lattice and factoring-based signatures[C]. The 15th International Conference on the Theory and Application of Cryptology and Information Security, Tokyo, 2009: 598–616. doi: 10.1007/978-3-642-10366-7_35.

LYUBASHEVSKY V. Lattice signatures without trapdoors[C]. The 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, 2012: 738–755. doi: 10.1007/978-3-642-29011-4_43.

DUCAS L, DURMUS A, LEPOINT T, et al. Lattice signatures and bimodal gaussians[C]. The 33rd Annual Cryptology Conference, Santa Barbara, 2013: 40–56. doi: 10.1007/978-3-642-40041-4_3.

AVANZI R, BOS J, DUCAS L, et al. Cryptographic suite for algebraic lattices[EB/OL]. https://pq-crystals.org/, 2019.

DUCAS L, LYUBASHEVSKY V, and PREST T. Efficient identity-based encryption over NTRU lattices[C]. The 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, 2014: 22–41. doi: 10.1007/978-3-662-45608-8_2.

BRUINDERINK L G, HÜLSING A, LANGE T, et al. Flush, gauss, and reload - a cache attack on the BLISS lattice-based signature scheme[C]. The 18th International Conference on Cryptographic Hardware and Embedded Systems, Santa Barbara, 2016: 323–345. doi: 10.1007/978-3-662-53140-2_16.

ESPITAU T, FOUQUE P, GÉRARD B, et al. Side-channel attacks on bliss lattice-based signatures: Exploiting branch tracing against strongswan and electromagnetic emanations in microcontrollers[C]. The 2017 ACM SIGSAC Conference on Computer and Communications Security, Dallas, 2017: 1857–1874. doi: 10.1145/3133956.3134028.

PESSL P, BRUINDERINK L G, and YAROM Y. To BLISS-B or not to be: Attacking strongSwan’s implementation of post-quantum signatures[C]. The 2017 ACM SIGSAC Conference on Computer and Communications Security, Dallas, 2017: 1843–1855. doi: 10.1145/3133956.3134023.

GÜNEYSU T, LYUBASHEVSKY V, and PÖPPELMANN T. Practical lattice-based cryptography: A signature scheme for embedded systems[C]. The 14th International Workshop on Cryptographic Hardware and Embedded Systems, Leuven, 2012: 530–547. doi: 10.1007/978-3-642-33027-8_31.

BAI Shi and GALBRAITH S D. An improved compression technique for signatures based on learning with errors[C]. Cryptographers’ Track at the RSA Conference, San Francisco, 2014: 28–47. doi: 10.1007/978-3-319-04852-9_2.

LENSTRA A K, LENSTRA H W Jr, and LOVÁSZ L. Factoring polynomials with rational coefficients[J]. Mathematische Annalen, 1982, 261(4): 515–534. doi: 10.1007/BF01457454

SCHNORR C P and EUCHNER M. Lattice basis reduction: Improved practical algorithms and solving subset sum problems[J]. Mathematical Programming, 1994, 66(1/3): 181–199. doi: 10.1007/BF01581144

LAARHOVEN T. Search problems in cryptography: From fingerprinting to lattice sieving[D]. [Ph.D. dissertation], Eindhoven University of Technology, 2015.

BECKER A, DUCAS L, GAMA N, et al. New directions in nearest neighbor searching with applications to lattice sieving[C]. The 27th Annual ACM-SIAM Symposium on Discrete Algorithms, Arlington, 2016: 10–24. doi: 10.1137/1.9781611974331.

LAARHOVEN T, MOSCA M, and VAN DE POL J. Finding shortest lattice vectors faster using quantum search[J]. Designs, Codes and Cryptography, 2015, 77(2/3): 375–400. doi: 10.1007/s10623-015-0067-5

AKLEYLEK S, ALKIM E, BARRETO P S L M, et al. qTesla[EB/OL]. https://qtesla.Org, 2019.

HOWGRAVE-GRAHAM N. A hybrid lattice-reduction and meet-in-the-middle attack against NTRU[C]. The 27th Annual International Cryptology Conference, Santa Barbara, 2007: 150–169. doi: 10.1007/978-3-540-74143-5_9.

ERDEM A, DUCAS L, PÖPPELMAN T, et al. Post-quantum key exchange-a new hope[C]. The 25th USENIX Security Symposium, Vancouver, 2016: 327–343.

施引文献

资源附件(0)

访问统计