高级搜索

理想格上格基的快速三角化算法研究

张洋 刘仁章 林东岱

引用本文: 张洋, 刘仁章, 林东岱. 理想格上格基的快速三角化算法研究[J]. 电子与信息学报, 2020, 42(1): 98-104. doi: 10.11999/JEIT190725 shu
Citation:  Yang ZHANG, Renzhang LIU, Dongdai LIN. Fast Triangularization of Ideal Latttice Basis[J]. Journal of Electronics and Information Technology, 2020, 42(1): 98-104. doi: 10.11999/JEIT190725 shu

理想格上格基的快速三角化算法研究

    作者简介: 张洋: 男,1991年生,博士生,研究方向为基于理想格算法的密码算法分析;
    刘仁章: 男,1989年生,博士,研究方向为格算法及格密码算法分析;
    林东岱: 男,1964年生,研究员,研究方向为密码学与安全协议、网络与系统安全、分布式密码计算
    通讯作者: 张洋,zhangyang9091@iie.ac.cn
摘要: 为了提高理想格上格基的三角化算法的效率,该文通过研究理想格上的多项式结构提出了一个理想格上格基的快速三角化算法,其时间复杂度为O(n3log2B),其中n是格基的维数,B是格基的无穷范数。基于该算法,可以得到一个计算理想格上格基Smith标准型的确定算法,且其时间复杂度也比现有的算法要快。更进一步,对于密码学中经常所使用的一类特殊的理想格,可以用更快的算法将三角化矩阵转化为格基的Hermite标准型。

English

    1. [1]

      FRUMKIN M A. Complexity questions in number theory[J]. Journal of Soviet Mathematics, 1985, 29(4): 1502–1517. doi: 10.1007/bf02104748

    2. [2]

      HUNG M S and ROM W O. An application of the Hermite normal form in integer programming[J]. Linear Algebra and its Applications, 1990, 140: 163–179. doi: 10.1016/0024-3795(90)90228-5

    3. [3]

      HAFNER J L and MCCURLEY K S. A rigorous subexponential algorithm for computation of class groups[J]. Journal of the American Mathematical Society, 1989, 2(4): 837–850. doi: 10.1090/S0894-0347-1989-1002631-0

    4. [4]

      HARTLEY B and HAWKES T O. Rings, Modules and Linear Algebra[M]. London: Chapman and Hall, 1970: 73.

    5. [5]

      MICCIANCIO D. Improving lattice based cryptosystems using the Hermite normal form[C]. International Conference on Cryptography and Lattices, Providence, 2001: 126–145. doi: 10.1007/3-540-44670-2_1.

    6. [6]

      LYUBASHEVSKY V and PREST T. Quadratic time, linear space algorithms for Gram-Schmidt orthogonalization and Gaussian sampling in structured lattices[C]. The 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, 2015: 789–815. doi: 10.1007/978-3-662-46800-5_30.

    7. [7]

      HAFNER J L and MCCURLEY K S. Asymptotically fast triangulation of matrices over rings[C]. The 1st Annual ACM-SIAM Symposium on Discrete Algorithm, San Francisco, 1990: 197–200.

    8. [8]

      LE GALL F. Powers of tensors and fast matrix multiplication[C]. The 39th International Symposium on Symbolic and Algebraic Computation, Kobe, 2014: 296–303. doi: 10.1145/2608628.2608664.

    9. [9]

      STORJOHANN A and LABAHN G. Asymptotically fast computation of Hermite normal forms of integer matrices[C]. 1996 International Symposium on Symbolic and Algebraic Computation, Zurich, 1996: 259–266.

    10. [10]

      DING Jintai and LINDNER R. Identifying ideal lattices[EB/OL]. http://eprint.iacr.org/2007/322, 2007.

    11. [11]

      ZHANG Yang, LIU Renzhang, and LIN Dongdai. Improved key generation algorithm for Gentry’s fully homomorphic encryption scheme[C]. The 20th International Conference on Information Security and Cryptology, Seoul, 2018: 93–111. doi: 10.1007/978-3-319-78556-1_6.

    12. [12]

      VON ZUR GATHEN J and GARHARD J. Modern Computer Algebra[M]. 3rd ed. Cambridge: Cambridge University Press, 2013: 313–332.

    13. [13]

      刘仁章. 格算法及其密码学应用[D]. [博士论文], 中国科学院大学数学与系统科学研究院, 2016.

    1. [1]

      王立辉, 闫守礼, 李清. 一种轻量级数据加密标准循环掩码实现方案. 电子与信息学报, 2020, 41(0): 1-8.

    2. [2]

      王延峰, 张桢桢, 王盼如, 孙军伟. 基于DNA链置换的两位格雷码减法器分子电路设计. 电子与信息学报, 2020, 42(0): 1-9.

    3. [3]

      刘文斌, 吴倩, 杜玉改, 方刚, 石晓龙, 许鹏. 基于个性化网络标志物的药物推荐方法研究. 电子与信息学报, 2020, 42(6): 1340-1347.

    4. [4]

      杨书新, 梁文, 朱凯丽. 基于三级邻居的复杂网络节点影响力度量方法. 电子与信息学报, 2020, 42(5): 1140-1148.

    5. [5]

      王年, 胡旭阳, 朱凡, 唐俊. 基于视图感知的单视图三维重建算法. 电子与信息学报, 2020, 42(0): 1-8.

    6. [6]

      刘新, 阎焜, 杨光耀, 叶盛波, 张群英, 方广有. UWB-MIMO穿墙雷达三维成像与运动补偿算法研究. 电子与信息学报, 2020, 41(0): 1-8.

    7. [7]

      段永强, 王振占, 张升伟. 风云三号(D)气象卫星微波湿温度计系统建模和仿真. 电子与信息学报, 2020, 42(6): 1549-1556.

    8. [8]

      孙军伟, 李智, 王延峰. 基于DNA链置换的三级联组合分子逻辑电路设计. 电子与信息学报, 2020, 42(6): 1401-1409.

  • 表 1  本原格向量序列

     输入:$ {\mathbb{Z}}\left[ {{x}} \right]$中$ f\left( x \right)$和$ g\left( x \right)$,次数分别为$ n$和$ m$,且$ n>m$;
        (1) 利用扩展欧几里得算法计算$ {\mathbb{Q}}[x]$上$ {r_i}^{'}\left( x \right)$, $ {s_i}^{'}\left( x \right)$,      $ {t_i}^{'}\left( x \right)$,使得$ {r_i}^{'}\left( x \right) = {r_{i - 2}}^{'}\left( x \right) + {q_i}^{'}\left( x \right){r_{i - 1}}^{'}\left( x \right)$      和${r_i}^{'}\left( x \right) = {s_i}^{'}\left( x \right)f\left( x \right) + $$ {t_i}^{'}\left( x \right)g\left( x \right)$成立,这里      $ i = 1,2, ··· ,l$;
        (2) 计算每一个$ {t_i}^{'}\left( x \right)$系数分母的最小公倍数$ {C_i}$,       $ i = 1,2, ··· ,l$;
        (3) 令$ {r_i}\left( x \right) = {r_i}^{'}\left( x \right) \cdot {C_i}$为余式序列中第$ i$个余式,      $ i = 1,2, ··· ,l$;
     输出:$ {r_1}\left( x \right)$, $ {r_2}\left( x \right)$, ···, $ {r_l}\left( x \right)$
    下载: 导出CSV

    表 2  理想格上格基的三角化

     输入:本原格向量序列,$ {r_0}\left( x \right)$, $ {r_1}\left( x \right)$, ···, $ {r_l}\left( x \right)$(向量形式为$ {{{r}}_{\bf 0}}$,
        $ {{{r}}_{\bf 1}}$, ···, $ {{{r}}_{ l}}$)
        (1) 令$ {{T}} \leftarrow {0^{n \times n}}$
        (2) 如果$ k \in {I_l},{{ T}_k}\left( x \right) = {r_l}\left( x \right){x^{n - k}},i \leftarrow l - 1$
        (3) 如果$ k \in {I_i}$,
        (a) 计算$ \phi $和ψ使得
          $ \phi {\rm{lc}}\left( {{r_i}} \right) + \psi {\rm{lc}}\left( {{{{T}}_{n - {n_{i + 1}}}}} \right) = {\rm{gcd}}\left( {\rm{lc}}\left( {{{{T}}_{n - {n_{i + 1}}}}} \right),\right.$
          $\left.{\rm{lc}}\left( {{r_i}} \right) \right) $
        (b) 令$ {{{T}}_{n - {n_i}}}\left( {{x}} \right) = \phi {r_i}\left( x \right) + \psi {{{T}}_{n - {n_{i + 1}}}}\left( x \right){x^{{\delta _i}}}$
        (c) 如果$ {\rm{lc}}\left( {{{{T}}_{n - {n_i}}}} \right) = 1$,则令
          $ {{{T}}_j}\left( x \right) = {{{T}}_{n - {n_i}}}\left( x \right){x^{n - {n_i} - j}}$,
          $ j = 1,2, ··· ,n - {n_i}$,并结束循环
        (d) 否则$ {{{T}}_k}\left( x \right) = {{{T}}_{n - {n_i}}}\left( x \right){x^{n - {n_i} - k}}$, $ i \leftarrow i - 1$
        (e) 如果$ i>0$,到(3)开始循环,否则结束循环
     输出:$ {{T}}$
    下载: 导出CSV
  • 加载中
计量
  • PDF下载量:  26
  • 文章访问数:  969
  • HTML全文浏览量:  382
文章相关
  • 通讯作者:  张洋, zhangyang9091@iie.ac.cn
  • 收稿日期:  2019-09-19
  • 录用日期:  2019-11-15
  • 网络出版日期:  2020-01-01
  • 刊出日期:  2020-01-01
通讯作者: 陈斌, bchen63@163.com
  • 1. 

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

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

/

返回文章