Efficient reductions among lattice problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient reductions among lattice problems

Full text

Pdf (377 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms table of contents

San Francisco, California

Pages 84-93

Year of Publication: 2008

Author

Daniele Micciancio

University of California at San Diego, La Jolla, CA

Sponsors

: SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 71, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

ABSTRACT

We give various deterministic polynomial time reductions among approximation problems on point lattices. Our reductions are both efficient and robust, in the sense that they preserve the rank of the lattice and approximation factor achieved. Our main result shows that for any γ ≥ 1, approximating all the successive minima of a lattice (and, in particular, approximately solving the Shortest Independent Vectors Problem, SIVPγ) within a factor γ reduces under deterministic polynomial time rank-preserving reductions to approximating the Closest Vector Problem (CVP) within the same factor γ. This solves an open problem posed by Blömer in (ICALP 2000). As an application, we obtain faster algorithms for the exact solution of SIVP that run in time n! · s^O(1) (where n is the rank of the lattice, and s the size of the input,) improving on the best previously known solution of Blömer (ICALP 2000) by a factor 3ⁿ. We also show that SIVP, CVP and many other lattice problems are equivalent in their exact version under deterministic polynomial time rank-preserving reductions.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Miklós Ajtai, The shortest vector problem in L2 is NP-hard for randomized reductions (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.10-19, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276705]
	2	M. Ajtai. Generating hard instances of lattice problems. Complexity of Computations and Proofs, Quaderni di Matematica, 13:1--32, 2004. Preliminary version in STOC 1996.
	3	Miklós Ajtai , Cynthia Dwork, A public-key cryptosystem with worst-case/average-case equivalence, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.284-293, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258604]
	4	Miklós Ajtai , Ravi Kumar , D. Sivakumar, A sieve algorithm for the shortest lattice vector problem, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.601-610, July 2001, Hersonissos, Greece [doi>10.1145/380752.380857]
	5	Miklos Ajtai , Ravi Kumar , D. Sivakumar, Sampling Short Lattice Vectors and the Closest Lattice Vector Problem, Proceedings of the 17th IEEE Annual Conference on Computational Complexity, p.53, May 21-24, 2002
	6	L Babai, On Lova´sz' lattice reduction and the nearest lattice point problem, Combinatorica, v.6 n.1, p.1-13, 1986 [doi>10.1007/BF02579403]
	7	W. Banaszczyk. New bounds in some transference theorems in the geometry of numbers. Mathematische Annalen, 296:625--635, 1993.
	8	Johannes Blömer, Closest Vectors, Successive Minima, and Dual HKZ-Bases of Lattices, Proceedings of the 27th International Colloquium on Automata, Languages and Programming, p.248-259, July 09-15, 2000
	9	J. Blömer and S. Naewe. Sampling methods for shortest vectors, closest vectors and successive minima. In Proceedings of ICALP '07, volume 4596 of LNCS, pages 65--77. Springer, July 2007.
	10	Johannes Blömer , Jean-Pierre Seifert, On the complexity of computing short linearly independent vectors and short bases in a lattice, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.711-720, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301441]
	11	E. F. Brickell and A. M. Odlyzko. Cryptanalysis: A survey of recent results. In G. J. Simmons, editor, Contemporary Cryptology, chapter 10, pages 501--540. IEEE Press, 1991.
	12	Jin-Yi Cai, A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor, Discrete Applied Mathematics, v.126 n.1, p.9-31, March 2003 [doi>10.1016/S0166-218X(02)00216-0]
	13	Henri Cohen, A course in computational algebraic number theory, Springer-Verlag New York, Inc., New York, NY, 1995
	14	I. Dinur , G. Kindler , R. Raz , S. Safra, Approximating CVP to Within Almost-Polynomial Factors is NP-Hard, Combinatorica, v.23 n.2, p.205-243, April 2003 [doi>10.1007/s00493-003-0019-y]
	15	Oded Goldreich , Shafi Goldwasser , Shai Halevi, Public-Key Cryptosystems from Lattice Reduction Problems, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.112-131, August 17-21, 1997
	16	O. Goldreich , D. Micciancio , S. Safra , J. -P. Seifert, Approximating shortest lattice vectors is not harder than approximating closet lattice vectors, Information Processing Letters, v.71 n.2, p.55-61, July 30, 1999 [doi>10.1016/S0020-0190(99)00083-6]
	17	V. Guruswami, D. Micciancio, and O. Regev. The complexity of the covering radius problem. Computational Complexity, 14(2):90--120, 2005. Preliminary version in CCC 2004.
	18	Ishay Haviv , Oded Regev, Tensor-based hardness of the shortest vector problem to within almost polynomial factors, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250859]
	19	A. Joux and J. Stern. Lattice reduction: A toolbox for the cryptanalyst. Journal of Cryptology, 11(3):161--185, 1998.
	20	Ravi Kannan, Minkowski's convex body theorem and integer programming, Mathematics of Operations Research, v.12 n.3, p.415-440, August 1, 1987 [doi>10.1287/moor.12.3.415]
	21	Subhash Khot, Hardness of approximating the shortest vector problem in lattices, Journal of the ACM (JACM), v.52 n.5, p.789-808, September 2005 [doi>10.1145/1089023.1089027]
	22	A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen, 261(4):513--534, Dec. 1982.
	23	Daniele Micciancio, The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant, SIAM Journal on Computing, v.30 n.6, p.2008-2035, 2001 [doi>10.1137/S0097539700373039]
	24	Daniele Micciancio, Almost Perfect Lattices, the Covering Radius Problem, and Applications to Ajtai's Connection Factor, SIAM Journal on Computing, v.34 n.1, p.118-169, 2005 [doi>10.1137/S0097539703433511]
	25	Daniele Micciancio, Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions, Computational Complexity, v.16 n.4, p.365-411, December 2007 [doi>10.1007/s00037-007-0234-9]
	26	Daniele Micciancio , S. Goldwasser, Complexity of Lattice Problems, Kluwer Academic Publishers, Norwell, MA, 2002
	27	Daniele Micciancio , Oded Regev, Worst-Case to Average-Case Reductions Based on Gaussian Measures, SIAM Journal on Computing, v.37 n.1, p.267-302, April 2007 [doi>10.1137/S0097539705447360]
	28	Phong Q. Nguyen , Jacques Stern, The Two Faces of Lattices in Cryptology, Revised Papers from the International Conference on Cryptography and Lattices, p.146-180, March 29-30, 2001
	29	Oded Regev, New lattice-based cryptographic constructions, Journal of the ACM (JACM), v.51 n.6, p.899-942, November 2004 [doi>10.1145/1039488.1039490]
	30	C. P. Schnorr, A hierarchy of polynomial time lattice basis reduction algorithms, Theoretical Computer Science, v.53 n.2-3, p.201-224, Aug. 1987 [doi>10.1016/0304-3975(87)90064-8]