FatSeal：一種基于格的高效簽名算法

謝天元; 李昊宇; 朱熠銘; 潘彥斌; 劉珍; 楊照民

doi:10.11999/JEIT190678

FatSeal：一種基于格的高效簽名算法

doi: 10.11999/JEIT190678

謝天元^{1, 2},
李昊宇^{1, 2},
朱熠銘^{1, 2},
潘彥斌^1, ,,
劉珍^{1, 2},
楊照民^{1, 2}

1.
中國科學院數(shù)學與系統(tǒng)科學研究院數(shù)學機械化重點實驗室北京 100190
2.
中國科學院大學數(shù)學科學學院北京 100049

基金項目: 國家自然科學基金(61572490)

詳細信息

作者簡介:
謝天元：女，1992年生，博士，研究方向為格密碼算法設計與分析

李昊宇：男，1990年生，博士，研究方向為格密碼算法設計與分析

朱熠銘：男，1994年生，博士，研究方向為格算法、編碼

潘彥斌：男，1982年生，副研究員，研究方向為格算法及格密碼算法分析

劉珍：女，1994年生，博士，研究方向為格算法及格密碼算法分析

楊照民：男，1995年生，碩士，研究方向為格算法、后斯諾登密碼

通訊作者:
潘彥斌　panyanbin@amss.ac.cn

中圖分類號: TN918.1
計量
- 文章訪問數(shù): 4336
- HTML全文瀏覽量: 2049
- PDF下載量: 222
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2019-09-04
- 修回日期: 2019-12-11
- 網(wǎng)絡出版日期: 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)

摘要

摘要: 當前基于格設計的能夠抵抗量子計算機攻擊的簽名方案是基于數(shù)論難題的傳統(tǒng)簽名方案的熱門候選替代。通過Fiat-Shamir變換以及拒絕采樣技術構造格簽名是一種重要方法，共有5個格簽名方案提交到美國國家標準與技術局的后量子算法項目中，基于Fiat-Shamir變換進行設計的有兩個方案。其中Dilithium是基于模錯誤學習(MLWE)問題構造的Fiat Shamir簽名，它的一個特性是在簽名算法中使用了高效簡潔的均勻采樣。Dilithium簽名方案構造在一般格上，為了獲得更緊湊的公鑰尺寸，Dilithium對公鑰進行了壓縮。另一方面，NTRU格上的密碼方案比一般格上的密碼方案在效率和參數(shù)尺寸上有更大的優(yōu)勢，該文給出了Dilithium簽名在NTRU格上的一個高效變種方案，在繼承Dilithium簡潔設計的基礎上，綜合了NTRU和拒絕采樣的技術優(yōu)勢而無需額外的壓縮處理，進一步提升了基于格的Fiat-Shamir簽名的效率。
- 數(shù)字簽名 /
- 格 /
- 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簽名方案的參數(shù)選取及迭代概率估計

$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安全強度下的參數(shù)大小(Byte)

體制	公鑰長度	私鑰長度	簽名長度
FatSeal-1024	2321	385	2048
FatSeal-2048	4984	719	4352

下載: 導出CSV

表 6 qTESLA簽名128 bit和256 bit安全強度下的參數(shù)大小(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)

訪問統(tǒng)計