Fast Triangularization of Ideal Latttice Basis

Yang ZHANG; Renzhang LIU; Dongdai LIN

doi:10.11999/JEIT190725

Volume 42 Issue 1

Jan. 2020

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2020 > 42(1): 98-104

Yang ZHANG, Renzhang LIU, Dongdai LIN. Fast Triangularization of Ideal Latttice Basis[J]. Journal of Electronics & Information Technology, 2020, 42(1): 98-104. doi: 10.11999/JEIT190725

Citation:

Yang ZHANG, Renzhang LIU, Dongdai LIN. Fast Triangularization of Ideal Latttice Basis[J]. Journal of Electronics & Information Technology, 2020, 42(1): 98-104. doi: 10.11999/JEIT190725

Yang ZHANG, Renzhang LIU, Dongdai LIN. Fast Triangularization of Ideal Latttice Basis[J]. Journal of Electronics & Information Technology, 2020, 42(1): 98-104. doi: 10.11999/JEIT190725

Citation:

Yang ZHANG, Renzhang LIU, Dongdai LIN. Fast Triangularization of Ideal Latttice Basis[J]. Journal of Electronics & Information Technology, 2020, 42(1): 98-104. doi: 10.11999/JEIT190725

PDF( 596 KB)

Fast Triangularization of Ideal Latttice Basis

doi: 10.11999/JEIT190725

1.
State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China
2.
School of Cyber Security,University of Chinese Academy of Sciences, Beijing 100049, China
3.
Westone Cryptologic Research Center, Beijing 100166, China

Received Date: 2019-09-19
Rev Recd Date: 2019-11-15

Available Online: 2020-01-01

Publish Date: 2020-01-21

Abstract

Abstract

To improve the efficiency of the triangularization of ideal lattice basis, a fast algorithm for triangularizing an ideal lattice basis is proposed by studying the polynomial structure, which runs in time O(n³log₂B), where n is the dimension of the lattice, B is the infinity norm of lattice basis. Based on the algorithm, a deterministic algorithm for computing the Smith Normal Form (SNF) of ideal lattice is given, which has the same time complexity and thus is faster than any previously known algorithms. Moreover, for a special class of ideal lattices, a method to transform such triangular bases into Hermite Normal Form (HNF) faster than previous algorithms will be present.
- Ideal lattice,
- Hermite Normal Form (HNF),
- Smith Normal Form (SNF),
- Triangularization

FullText(HTML)

References(13)

References

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

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

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

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

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.

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.

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.

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.

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.

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

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.

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

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

Relative Articles

Supplements(0)

Cited By

Proportional views