Computer Science – Cryptography and Security
Scientific paper
2007-05-07
Dans Advances in Cryptology - Crypto'07 4622 (2007) 170-186
Computer Science
Cryptography and Security
Scientific paper
10.1007/978-3-540-74143-5_10
The security of lattice-based cryptosystems such as NTRU, GGH and Ajtai-Dwork essentially relies upon the intractability of computing a shortest non-zero lattice vector and a closest lattice vector to a given target vector in high dimensions. The best algorithms for these tasks are due to Kannan, and, though remarkably simple, their complexity estimates have not been improved since more than twenty years. Kannan's algorithm for solving the shortest vector problem is in particular crucial in Schnorr's celebrated block reduction algorithm, on which are based the best known attacks against the lattice-based encryption schemes mentioned above. Understanding precisely Kannan's algorithm is of prime importance for providing meaningful key-sizes. In this paper we improve the complexity analyses of Kannan's algorithms and discuss the possibility of improving the underlying enumeration strategy.
Hanrot Guillaume
Stehlé Damien
No associations
LandOfFree
Improved Analysis of Kannan's Shortest Lattice Vector Algorithm does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Improved Analysis of Kannan's Shortest Lattice Vector Algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improved Analysis of Kannan's Shortest Lattice Vector Algorithm will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-598861