Abstract
We present a novel practical algorithm that given a lattice basis b1, ..., bn finds in O(n 2( k/6 )k/4) average time a shorter vector than b 1 provided that b 1 is ( k/6 )n/(2k) times longer than the length of the shortest, nonzero lattice vector. We assume that the given basis b 1, ..., b n has an orthogonal basis that is typical for worst case lattice bases. The new reduction method samples short lattice vectors in high dimensional sublattices, it advances in sporadic big jumps. It decreases the approximation factor achievable in a given time by known methods to less than its fourth-th root. We further speed up the new method by the simple and the general birthday method.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
M. Ajtai, The shortest vector problem in L2 is NP-hard for randomised reductions. Proc. 30th STOC, pp. 10–19, 1998.
M. Ajtai, The worst-case behaviour of Schnorr’s algorithm approximating the shortest nonzero vector in a lattice. Preprint 2002.
M. Ajtai, R. Kumar, and D. Sivakumar, A sieve algorithm for the shortest lattice vector problem. Proc. 33th STOC, 2001.
P. Camion, and J. Patarin, The knapsack hash function proposed at Crypto’89 can be broken.Proc. Eurocrypt’91, LNCS 457, Springer-Verlag, pp. 39–53, 1991.
P. van Emde Boas, Another NP-complete partition problem and the complexity of computing short vectors in a lattice. Mathematics Department, University of Amsterdam, TR 81-04, 1981.
O. Goldreich, S. Goldwasser, and S. Halevi, Public key cryptosystems from lattice reduction problems. Proc. Crypto’97, LNCS 1294, Springer-Verlag, pp. 112–131, 1997.
B. Helfrich, Algorithms to construct Minkowski reduced and Hermite reduced bases. Theor. Comp. Sc.41, pp. 125–139, 1985.
R. Kannan, Minkowski’s convex body theorem and integer programming. Mathematics of Operations Research12 pp. 415–440, 1987, Preliminary version in Proc. 13th STOC, 1983.
D. E. Knuth, The Art of Computer Programming, Vol 1, Fundamental Algorithms. 3rd Edidtion, Addison-Wesley, Reading, 1997.
H. Koy and C. P. Schnorr, Segment and strong Segment LLL-reduction of lattice bases. Preprint University Frankfurt, 2002, http://www.mi.informatik.uni-frankfurt.de/research/papers.html
H. Koy and C. P. Schnorr, Segment LLL-reduction of lattice bases. Proc. CaLC 2001, LNCS 2146, Springer-Verlag, pp. 67–80, 2001.
H. Koy, Primale/duale Segment-Reduktion von Gitterbasen. Slides of a lecture, Frankfurt, December 2000.
H. Koy and C. P. Schnorr, Segment LLL-reduction of lattice bases with floating point orthogonalization. Proc. CaLC 2001, LNCS 2146, Springer-Verlag, pp. 81–96, 2001.
A. K. Lenstra, H. W. Lenstra, and L. Lovász, Factoring polynomials with rational coefficients. Math. Ann.261, pp. 515–534, 1982.
D. Micciancio, The shortest vector in a lattice is NP-hard to approximate to within some constant. Proc. 39th Symp. FOCS, pp. 92–98, 1998, full paper SIAM Journal on Computing, 30 (6), pp. 2008-2035, March 2001.
P. Q. Nguyen, Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from Crypto’97. Proc. Crypto’99, LNCS 1666, Springer-Verlag, pp. 288–304, 1999.
P. Q. Nguyen and J. Stern, Lattice reduction in cryptology: an update. Proc. ANTS-IV, LNCS 1838, Springer-Verlag, pp. 188–112. full version http://www.di.ens.fr/~pnguyen,stern/
V. Shoup, Number Theory Library. http://www.shoup.net/ntl
C. P. Schnorr, A hierarchy of polynomial time lattice basis reduction algorithms. Theor. Comp. Sc.53, pp. 201–224, 1987.
C. P. Schnorr, A more efficient algorithm for lattice reduction. J. of Algor.9, 47–62, 1988.
C. P. Schnorr and M. Euchner, Lattice Basis Reduction and Solving Subset Sum Problems. Fundamentals of Comput. Theory, Lecture Notes in Comput. Sci., 591, Springer, New York, 1991, pp. 68–85. The complete paper appeared in Math. Programming Studies, 66A, 2, pp. 181-199, 1994.
D. Wagner, A Generalized Birthday Problem. Proceedings Crypto’02, LNCS 2442, Springer-Verlag, pp. 288–303, 2002. full version http://www.cs.berkeley.edu/~daw/papers/
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Schnorr, C.P. (2003). Lattice Reduction by Random Sampling and Birthday Methods. In: Alt, H., Habib, M. (eds) STACS 2003. STACS 2003. Lecture Notes in Computer Science, vol 2607. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36494-3_14
Download citation
DOI: https://doi.org/10.1007/3-540-36494-3_14
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00623-7
Online ISBN: 978-3-540-36494-8
eBook Packages: Springer Book Archive