The shortest vector problem in L2 is NP-hard for randomized reductions (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The shortest vector problem in L2 is NP-hard for randomized reductions (extended abstract)

Full text

Pdf (1.32 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirtieth annual ACM symposium on Theory of computing table of contents

Dallas, Texas, United States

Pages: 10 - 19

Year of Publication: 1998

ISBN:0-89791-962-9

Author

Miklós Ajtai

IBM Almaden Research Center, San Jose, CA

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): 53, Citation Count: 24

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	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/276698.276705 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.

	ABSS	S. Arora, L. Babai, J. Stern, Z. Sweedyk, The hard. ness of approximate optima in lattices, codes and systems of linear equations, Prec. 34-th Annual Syrup. Found. Computer Science, 1993, pp. 724-733.
	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]
	Adl	L. Adleman, Factoring and Lattice Reduction, Manuscript, 1995.
	Ajt1	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]
	Ajt2	M. Ajtai, The Shortest Vector Problem in/,2 is N/:'- hard for Randomized Reductions. Electronic Colloquium on Computational Complexity, 1997 http://www, ecce.uni-trier, de/eccc/
	AS	N. Aion, J. Spencer, The Probabilisitc Method, John Wiley & Sons, 1992.
	AC	J.-Y. Cai , A. Nerurkar, Approximating the SVP to within a Factor is NP-Hard under Randomized Reductions, Proceedings of the Thirteenth Annual IEEE Conference on Computational Complexity, p.46, June 15-18, 1998
	Ch	H. Chernoff, A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the Sum of Observations, Annals of Mathematical Statistics 1952, (23), pp 493..507.
	vEB	P. Van Erode Boas, Another NP-complet~ partition problem and the complexity of computing short vectors in a lattice, Tech. Report 81-04, Dept. of Mathematics, Univ. of Amsterdam, 1980.
	GG	O. Goldreich, S. Goldwasser, On the Limits of Non- Approximability of Lattice Problems, Electronic Colloquium, 1997, on Computational Complexity, http ://www. ecce.uni-trier, de/eccc/
	GGH1	O. Goldreich, S. Goldwasser, S. Halevi, Collisionfree hashing from lattice problems, Electronic Colloquium, 1996, on Computational Complexity, http:l/www, eccc.uni-trier, de/eccc/
	GGH2	O. Goldreich, S. Goldwasser, S. Halevi, Publickcy cryptosystems from lattice reduction problems, Electronic Colloquium on Computational Complexity, 1996, http://www, ee~~.uni-trier, de/eccc/
	K	R, M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computation, e.d. R, E, Miller and J. W. Thatcher, New York: Plenum Press, 1972
	LLS	J, Lagarias, H.W Lenstra and, C. P. Schnorr, Korkine- Zolotarev bases and successive minima of a lattice and its reciprocal lattice, Combinatorica 10 (1990), 333-348
	S	N. $auer On the density of families of sets, Journal of Combinatorial Theory, Series A13, 1972, 145..147
	V1	A, Vardy, The Intractability of Computing the Minimum Distance Code, Preprint
	V2	Alexander Vardy, Algorithmic complexity in coding theory and the minimum distance problem, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.92-109, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258559]
	VC	V,N, Vapnik and Ya. Chervonenkis, On the uniform convergence of relative frequencies of ~venff to their probabilities, Theory of Probability Applications 1971, (16), 264.. 280.

CITED BY 24

	Ian F. Blake , Theodoulos Garefalakis, On the Security of the Digital Signature Algorithm, Designs, Codes and Cryptography, v.26 n.1-3, p.87-96
	Simon R. Blackburn , Domingo Gomez-Perez , Jaime Gutierrez , Igor E. Shparlinski, Reconstructing noisy polynomial evaluation in residue rings, Journal of Algorithms, v.61 n.2, p.47-59, November, 2006
	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
	Ali Akhavi, The optimal LLL algorithm is still polynomial in fixed dimension, Theoretical Computer Science, v.297 n.1-3, p.3-23, 17 March 2003
	Ali Akhavi, Random lattices, threshold phenomena and efficient reduction algorithms, Theoretical Computer Science, v.287 n.2, p.359-385, 28 September 2002
	Johannes Merkle, Multi-round passive attacks on server-aided RSA protocols, Proceedings of the 7th ACM conference on Computer and communications security, p.102-107, November 01-04, 2000, Athens, Greece
	Denis Xavier Charles, Counting lattice vectors, Journal of Computer and System Sciences, v.73 n.6, p.962-972, September, 2007
	Claus Peter Schnorr, Fast LLL-type lattice reduction, Information and Computation, v.204 n.1, p.1-25, January 2006
	Lane A. Hemaspaandra, Complexity theory, ACM SIGACT News, v.32 n.3, p.40-52, 09/01/2001
	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
	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
	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
	Uriel Feige , Daniele Micciancio, The inapproximability of lattice and coding problems with preprocessing, Journal of Computer and System Sciences, v.69 n.1, p.45-67, August 2004
	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
	Daniele Micciancio, Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions, Computational Complexity, v.16 n.4, p.365-411, December 2007
	Subhash Khot, Hardness of approximating the shortest vector problem in high lp norms, Journal of Computer and System Sciences, v.72 n.2, p.206-219, March 2006
	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
	Jörg Rothe, Some facets of complexity theory and cryptography: A five-lecture tutorial, ACM Computing Surveys (CSUR), v.34 n.4, p.504-549, December 2002
	Chris Peikert , Alon Rosen, Lattices that admit logarithmic worst-case to average-case connection factors, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Dorit Aharonov , Oded Regev, Lattice problems in NP ∩ coNP, Journal of the ACM (JACM), v.52 n.5, p.749-765, September 2005
	Karen Aardal , Robert Weismantel , Laurence A. Wolsey, Non-standard approaches to integer programming, Discrete Applied Mathematics, v.123 n.1-3, p.5-74, 15 November 2002
	Andrej Bogdanov , Luca Trevisan, Average-case complexity, Foundations and Trends® in Theoretical Computer Science, v.2 n.1, p.1-106, October 2006
	David S. Johnson, The NP-completeness column, ACM Transactions on Algorithms (TALG), v.1 n.1, p.160-176, July 2005
	Jin-Yi Cai , Hong Zhu, Progress in computational complexity theory, Journal of Computer Science and Technology, v.20 n.6, p.735-750, November 2005