Two Types of Special Bases for Integral Lattices

详细信息    查看全文

• 关键词：Lattice ; Gram matrix ; Unimodular congruence transformation ; Orthogonality
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9503
• 期：1
• 页码：87-95
• 全文大小：170 KB
• 参考文献：1.Boneh, D., Durfee, G.: Cryptanalysis of RSA with private key \(d\) less than \(N^{0.292}\) . In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 1–11. Springer, Heidelberg (1999)CrossRef
  2.Ducas, L., Durmus, A., Lepoint, T., Lyubashevsky, V.: Lattice signatures and bimodal gaussians. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 40–56. Springer, Heidelberg (2013)CrossRef
  3.Eichler, M.: Note zur Theorie der Kristallgitter. Math. Ann. 125, 51–55 (1952)CrossRef MATH MathSciNet
  4.Garg, S., Gentry, C., Halevi, S.: Candidate multilinear maps from ideal lattices. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 1–17. Springer, Heidelberg (2013)CrossRef
  5.Gauss, C.F.: Disquisitiones Arithmeticae. Springer, New York (1801)MATH
  6.Gentry, C.: Fully homomorphic encryption using ideal lattices. In: 41st ACM Symposium on Theory of Computing, pp. 169–178. ACM, Maryland (2009)
  7.Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: 40st ACM Symposium on Theory of Computing, pp. 197–206. ACM, Canada (2008)
  8.Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: a ring-based public key cryptosystem. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 267–288. Springer, Heidelberg (1998)CrossRef
  9.Lagrange, J.L.: Recherches d’arithmétique. Nouveaux Mémoires de l’Académie de Berlin (1773)
  10.Lenstra, A.K., Lenstra, H.W., Lovász, L.: Factoring polynomials with rational coeffcients. Math. Ann. 261, 515–534 (1982)CrossRef MATH MathSciNet
  11.Odlyzko, A.M.: The rise and fall of knapsack cryptosystems. In: Symposia in Applied Mathematics, vol. 42, pp. 75–88. A.M.S. (1990)
  12.Shoup, V.: NTL: A library for ng number theory. http://​www.​shoup.​net/​ntl/​
  
• 作者单位：Renzhang Liu (15) (16)
  Yanbin Pan (15) (16)
  
  15. Key Laboratory of Mathematics Mechanization, Academy of Mathematics and Systems Science, NCMIS, Chinese Academy of Sciences, Beijing, 100190, China
  16. Science and Technology on Communication Security Laboratory, Chengdu, 610041, China
  
• 丛书名：Information Security Applications
• ISBN：978-3-319-31875-2
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

Lattice basis reduction algorithms, such as LLL, play a very important role in cryptography, which usually aim to find a lattice basis with good “orthogonality”. However, not every lattice has an orthogonal basis, which means that we can only find some nearly orthogonal bases for these lattices. In this paper, we show that every integral lattice must have two types of special bases related to the orthogonality. First, any integral lattice with rank more than 1 has a class of bases such that the angle between any two basis vectors lies in \([\frac{\pi }{3},\frac{2\pi }{3}]\). Second, any integral lattice with rank more than 2 has a class of bases such that any basis can be divided into two sets and the vectors in every set are pairwise orthogonal. To obtain such results, we introduce the technique called unimodular congruence transformation for the Gram matrix.