高级搜索

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

张洋 刘仁章 林东岱

引用本文: 张洋, 刘仁章, 林东岱. 理想格上格基的快速三角化算法研究[J]. 电子与信息学报, 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, 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]

      张国雯, 高军, 曹祥玉, 杨欢欢, 李思佳. 基于三种反射型单元共享孔径的新型宽带低RCS反射屏设计. 电子与信息学报,

    2. [2]

      江明明, 郭宇燕, 余磊, 宋万干, 魏仕民. 有效的标准模型下格上基于身份的代理重加密. 电子与信息学报,

    3. [3]

      黄海, 冯新新, 刘红雨, 厚娇, 赵玉迎, 尹莉莉, 姜久兴. 基于随机加法链的高级加密标准抗侧信道攻击对策. 电子与信息学报,

    4. [4]

      罗忠涛, 卢鹏, 张杨勇, 张刚. 抑制脉冲型噪声的限幅器自适应设计. 电子与信息学报,

    5. [5]

      徐金甫, 吴缙, 李军伟, 曲彤洲, 董永兴. 基于敏感度混淆机制的控制型物理不可克隆函数研究. 电子与信息学报,

    6. [6]

      冯霞, 唐菱, 卢敏. 基于禁忌搜索算法的机场外航服务人员班型生成研究. 电子与信息学报,

    7. [7]

      高丽江, 杨海钢, 李威, 郝亚男, 刘长龙, 石彩霞. 具有高资源利用率特征的改进型查找表电路结构与优化方法. 电子与信息学报,

    8. [8]

      王剑书, 樊养余, 杜瑞, 吕国云. 适用于二维阵列的无格稀疏波达方向估计算法. 电子与信息学报,

    9. [9]

      周治平, 李智聪. 无可信第三方的数据匿名化收集协议. 电子与信息学报,

    10. [10]

      李扬, 张伟涛, 楼顺天. 基于联合对角化的声信号深度卷积混合盲分离方法. 电子与信息学报,

    11. [11]

      龚晓峰, 毛蕾, 林秋华, 徐友根, 刘志文. 基于四阶累积量张量联合对角化的多数据集联合盲源分离. 电子与信息学报,

    12. [12]

      胡淼, 阮泽辉, 李鹏, 曹保锋, 周雪芳, 孙佳琦, 胡喜明, 叶晟. 雷电测向正交磁环天线的测角误差矫正. 电子与信息学报,

    13. [13]

      徐保庆, 赵永波, 庞晓娇. 基于实值处理的联合波束域双基地MIMO雷达测角算法. 电子与信息学报,

    14. [14]

      徐丹, 符吉祥, 孙光才, 邢孟道, 苏涛, 保铮. 空间目标的短时三维几何重构方法. 电子与信息学报,

    15. [15]

      胡健, 罗迎, 张群, 康乐, 何其芳. 空间旋转目标窄带雷达干涉式三维成像与微动特征提取. 电子与信息学报,

    16. [16]

      周洋, 吴佳忆, 陆宇, 殷海兵. 面向三维高效视频编码的深度图错误隐藏. 电子与信息学报,

    17. [17]

      王伟, 胡子英, 龚琳舒. MIMO雷达三维成像自适应Off-grid校正方法. 电子与信息学报,

    18. [18]

      高丽江, 杨海钢, 张超. 低热梯度导向的三维FPGA互连通道网络架构研究. 电子与信息学报,

    19. [19]

      任凯强, 孙正波. 基于虚拟参考站的同步三星时差定位系统广域差分校正算法. 电子与信息学报,

    20. [20]

      陈莹, 陈湟康. 基于多模态生成对抗网络和三元组损失的说话人识别. 电子与信息学报,

  • 表 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),{\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下载量:  6
  • 文章访问数:  338
  • HTML全文浏览量:  77
文章相关
  • 通讯作者:  张洋, zhangyang9091@iie.ac.cn
  • 收稿日期:  2019-09-19
  • 录用日期:  2019-11-15
  • 网络出版日期:  2020-01-01
通讯作者: 陈斌, bchen63@163.com
  • 1. 

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

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

/

返回文章