高级搜索

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

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

引用本文: 谢天元, 李昊宇, 朱熠铭, 潘彦斌, 刘珍, 杨照民. FatSeal:一种基于格的高效签名算法[J]. 电子与信息学报, 2020, 42(2): 333-340. doi: 10.11999/JEIT190678 shu
Citation:  Tianyuan XIE, Haoyu LI, Yiming ZHU, Yanbin PAN, Zhen LIU, Zhaomin YANG. FatSeal: An Efficient Lattice-based Signature Algorithm[J]. Journal of Electronics and Information Technology, 2020, 42(2): 333-340. doi: 10.11999/JEIT190678 shu

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

    作者简介: 谢天元: 女,1992年生,博士,研究方向为格密码算法设计与分析;
    李昊宇: 男,1990年生,博士,研究方向为格密码算法设计与分析;
    朱熠铭: 男,1994年生,博士,研究方向为格算法、编码;
    潘彦斌: 男,1982年生,副研究员,研究方向为格算法及格密码算法分析;
    刘珍: 女,1994年生,博士,研究方向为格算法及格密码算法分析;
    杨照民: 男,1995年生,硕士,研究方向为格算法、后斯诺登密码
    通讯作者: 潘彦斌,panyanbin@amss.ac.cn
  • 基金项目: 国家自然科学基金(61572490)

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

English

    1. [1]

      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.

    2. [2]

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

    3. [3]

      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.

    4. [4]

      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.

    5. [5]

      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.

    6. [6]

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

    7. [7]

      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.

    8. [8]

      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.

    9. [9]

      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.

    10. [10]

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

    11. [11]

      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.

    12. [12]

      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.

    13. [13]

      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.

    14. [14]

      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.

    15. [15]

      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.

    16. [16]

      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.

    17. [17]

      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

    18. [18]

      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

    19. [19]

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

    20. [20]

      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.

    21. [21]

      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

    22. [22]

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

    23. [23]

      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.

    24. [24]

      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.

  • 表 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 $迭代概率(%)
    1024T(257, 256)28671210644358402010.2
    2048T(413, 412)72499328787906242411.4
    下载: 导出CSV

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

    体制公钥长度私钥长度签名长度
    FatSeal-102423213852048
    FatSeal-204849847194352
    下载: 导出CSV

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

    体制公钥长度私钥长度签名长度
    qTESLA-Ⅱ233616002144
    qTESLA-Ⅴ502435204640
    下载: 导出CSV

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

    模型体制$b$$N$${r_1}$比特安全性
    classicalFatSeal-1024510177091150
    quantumFatSeal-1024522179975139
    plausibleFatSeal-1024549186540115
    classicalFatSeal-204811303440240331
    quantumFatSeal-204811573503207307
    plausibleFatSeal-204812193646132253
    下载: 导出CSV

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

    体制攻击模型mbclassicalquantumplausible
    FatSeal-1024primal874503147133104
    FatSeal-1024dual862502146133104
    FatSeal-2048primal16711076314285223
    FatSeal-2048dual16971072313284222
    下载: 导出CSV

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

    模型体制$b$$w$比特安全性
    classicalFatSeal-10245772048181
    quantumFatSeal-10245772048166
    plausibleFatSeal-10245772048132
    classicalFatSeal-204812764039379
    quantumFatSeal-204812784041344
    plausibleFatSeal-204812844049270
    下载: 导出CSV
  • 加载中
计量
  • PDF下载量:  52
  • 文章访问数:  902
  • HTML全文浏览量:  518
文章相关
  • 通讯作者:  潘彦斌, panyanbin@amss.ac.cn
  • 收稿日期:  2019-09-04
  • 录用日期:  2019-12-11
  • 网络出版日期:  2019-12-19
  • 刊出日期:  2020-02-01
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

/

返回文章