FatSeal: An Efficient Lattice-based Signature Algorithm

Tianyuan XIE; Haoyu LI; Yiming ZHU; Yanbin PAN; Zhen LIU; Zhaomin YANG

doi:10.11999/JEIT190678

Volume 42 Issue 2

Feb. 2020

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2020 > 42(2): 333-340

Tianyuan XIE, Haoyu LI, Yiming ZHU, Yanbin PAN, Zhen LIU, Zhaomin YANG. FatSeal: An Efficient Lattice-based Signature Algorithm[J]. Journal of Electronics & Information Technology, 2020, 42(2): 333-340. doi: 10.11999/JEIT190678

Citation:

Tianyuan XIE, Haoyu LI, Yiming ZHU, Yanbin PAN, Zhen LIU, Zhaomin YANG. FatSeal: An Efficient Lattice-based Signature Algorithm[J]. Journal of Electronics & Information Technology, 2020, 42(2): 333-340. doi: 10.11999/JEIT190678

Citation:

PDF( 592 KB)

FatSeal: An Efficient Lattice-based Signature Algorithm

doi: 10.11999/JEIT190678

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)

Received Date: 2019-09-04
Rev Recd Date: 2019-12-11

Available Online: 2019-12-19

Publish Date: 2020-02-19

Abstract

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

FullText(HTML)

References(24)

References

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.

Relative Articles

Supplements(0)

Cited By

Proportional views