On the complexity of computing short linearly independent vectors and short bases in a lattice

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the complexity of computing short linearly independent vectors and short bases in a lattice

Full text

Pdf (786 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-first annual ACM symposium on Theory of computing table of contents

Atlanta, Georgia, United States

Pages: 711 - 720

Year of Publication: 1999

ISBN:1-58113-067-8

Authors

Johannes Blömer	Institut für Theoretische Informatik, ETH Zürich
Jean-Pierre Seifert	Department of Mathematics and Computer Science, University of Frankfurt

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 25, Citation Count: 6

Additional Information:

references cited by index terms collaborative colleagues

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

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/301250.301441 What is a DOI?

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.

	A1	M. Ajtai, Generating hard instances of lattice problems (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.99-108, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237838]
	A2	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]
	A3	M. Ajtai, "Worst-Case Complexity, Average-Case Complexity and Lattice Problems", Proc. International Congress of Mathematicians 1998, Vol. III, pp. 421-428.
	ABSS	Sanjeev Arora , László Babai , Jacques Stern , Z. Sweedyk, The hardness of approximate optima in lattices, codes, and systems of linear equations, Journal of Computer and System Sciences, v.54 n.2, p.317-331, April 1997 [doi>10.1006/jcss.1997.1472]
	AD	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]
	AL	Sanjeev Arora , Carsten Lund, Hardness of approximations, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
	B	L Babai, Trading group theory for randomness, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.421-429, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22192]
	Ba	W. Banaszcyk, ':New Bounds in Some Transference Theorems in the Geometry of Numbers", Mathematische A nnalen Vol. 296, pp. 625-635, 1993.
	C	J. W. S. Cassels, An Introduction to the Geometry of Numbers, Springer-Verlag, 1971.
	Ca1	J. Y. Cai, "A New Transference Theorem and Apalications to Ajtai's Connection Factor", Electronic Colloquium on Computational Complexity, TR98-05, 1998.
	Ca2	Jin-Yi Cai, A relation of primal-dual lattices and the complexity of shortest lattice vector problem, Theoretical Computer Science, v.207 n.1, p.105-116, Oct. 28, 1998 [doi>10.1016/S0304-3975(98)00058-9]
	CN	Jin-yi Cai , Ajay P. Nerurkar, An Improved Worst-Case to Average-Case Connection for Lattice Problems, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.468, October 19-22, 1997
	DKS	I. Dinur , G. Kindler , S. Safra, Approximating-CVP to within Almost-Polynomial Factors is NP-Hard, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.99, November 08-11, 1998
	GG	Oded Goldreich , Shafi Goldwasser, On the limits of non-approximability of lattice problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.1-9, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276704]
	GGH	O. Goldreich, S. Goldwasser, and S. Italevi, "Collision-Free Hashing from Lattice Problems", Electronic Colloquium on Computational Complexity, TR96-042, 1996.
	GMSS	O. Goldreich, D. Micciancio, S. Safra, J.-P. Seifert, "Approximating shortest lattice vectors is not harder than approximating closest lattice vectors", Electronic Colloquium on Computational Complexity, TR99-002, 1999.
	H	Martin Henk, Note on shortest and nearest lattice vectors, Information Processing Letters, v.61 n.4, p.183-188, Feb. 1997 [doi>10.1016/S0020-0190(97)00019-7]
	K1	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]
	K2	R. Kannan, "Algorithmic Geometry of Numbers", Ann. Rev. Comput. Science Vol. 2, pp. 231-267, 1987.
	L	L. Lovasz, An Algorithmic Theory of Graphs, Numbers and Convexity, SIAM, 1986.
	LLS	J. Lagarias, H. W. Lenstra, C. P. Schnorr, "Korkin-Zolotarev Bases and Successive Minima of Lattice a~d its Reciprocal Lattice", Combinatorica Vol. 10, No. 4, pp. 333-348, 1990.
	M	Daniele Micciancio, The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.92, November 08-11, 1998
	MH	J. Milnor, D. Husemoller, Symmetric Bilinear Forms, Springer-Verlag, 1973.

CITED BY 6

	Daniele Micciancio, Improved cryptographic hash functions with worst-case/average-case connection, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Claus Peter Schnorr, Fast LLL-type lattice reduction, Information and Computation, v.204 n.1, p.1-25, January 2006
	Daniele Micciancio, Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions, Computational Complexity, v.16 n.4, p.365-411, December 2007
	Oded Regev , Ricky Rosen, Lattice problems and norm embeddings, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Daniele Micciancio, Efficient reductions among lattice problems, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.84-93, January 20-22, 2008, San Francisco, California
	Johannes Blömer , Stefanie Naewe, Sampling methods for shortest vectors, closest vectors and successive minima, Theoretical Computer Science, v.410 n.18, p.1648-1665, April, 2009