FatSeal:一種基于格的高效簽名算法
doi: 10.11999/JEIT190678
-
1.
中國科學院數(shù)學與系統(tǒng)科學研究院數(shù)學機械化重點實驗室 北京 100190
-
2.
中國科學院大學數(shù)學科學學院 北京 100049
FatSeal: An Efficient Lattice-based Signature Algorithm
-
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
-
摘要: 當前基于格設計的能夠抵抗量子計算機攻擊的簽名方案是基于數(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.-
Key words:
- Digital signature /
- Lattice /
- Fiat-Shamir transform /
- Post-quantum /
- Rejection sampling
-
表 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
-
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. -
計量
- 文章訪問數(shù): 4336
- HTML全文瀏覽量: 2049
- PDF下載量: 222
- 被引次數(shù): 0