A public-key cryptosystem with worst-case/average-case equivalence

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A public-key cryptosystem with worst-case/average-case equivalence

Full text

Pdf (1.53 MB)

Source

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

El Paso, Texas, United States

Pages: 284 - 293

Year of Publication: 1997

ISBN:0-89791-888-6

Authors

Miklós Ajtai	IBM Almaden Research Center, Dept. K53/B2, 650 Harry Rd., San Jose, CA
Cynthia Dwork	IBM Almaden Research Center, Dept. K53/B2, 650 Harry Rd., San Jose, CA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 14, Downloads (12 Months): 100, Citation Count: 36

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/258533.258604 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.

	1	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]
	2	M. Ajtai, C. Dwork, A Public-Key Cryptosystem with Average-Case/Worst-Case Equivalence, Electronic Colloquium on Computational Complexity TR96-065, http:// www.eccc.uni-trier.de/ eccc-local/Lists/TR- 1996.html
	3	M. Ajtai and R. Fag,in, Reachability is Harder for Directed than for Unidirected Graphs, J. Symbolic Logic 55(1), pp. 113 - 150, 1990
	4	J.W.S. Cassels, An Introduction to the Geometry of' Numbers, Springer, 1959
	5	W. Diffie and M.E. Hellman, New Directions in Cryptography, IEEE Transactions on Information Theory, v. IT-22, n.6, pp. 644-654, 1976
	6	O. Goldreich, Lecture Notes on Foundations of Cryptography, http://www.wisdom.weizmann.ac.il/people/ homepages/oded/ln89.html, 1989 (see also, Foundations of Cryptography (Fi'agments of a Book), http://www, wisdom, weizmann, ac.il/people/homepages/ oded/frag.html)
	7	O. Goldreich , S. Goldwasser , S. Halevi, Public-Key Cryptosystems from Lattice Reduction Problems, Massachusetts Institute of Technology, Cambridge, MA, 1996
	8	P.M. Gruber, C.G.Lekkerkerker, Geometry of Numbers, North-Holland, 1987
	9	M. GrStschel, L. Lov~isz, A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer, Algorithms and Combinatorics 2, 1988
	10	R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]

CITED BY 37

	Sanjeev Arora, The approximability of NP-hard problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.337-348, May 24-26, 1998, Dallas, Texas, United States
	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
	Cynthia Dwork , Larry Stockmeyer, 2-round zero knowledge and proof auditors, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Oded Regev, On lattices, learning with errors, random linear codes, and cryptography, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	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
	Oded Regev, New lattice based cryptographic constructions, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	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
	Lane A. Hemaspaandra, Complexity theory, ACM SIGACT News, v.32 n.3, p.40-52, 09/01/2001
	Werner Backes , Susanne Wetzel, Heuristics on lattice basis reduction in practice, Journal of Experimental Algorithmics (JEA), 7, p.1, 2002
	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
	Oded Regev, New lattice-based cryptographic constructions, Journal of the ACM (JACM), v.51 n.6, p.899-942, November 2004
	Miklós Ajtai, Representing hard lattices with O(n log n) bits, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	David S. Johnson, The NP-completeness column, ACM Transactions on Algorithms (TALG), v.1 n.1, p.160-176, July 2005
	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
	Dorit Aharonov , Oded Regev, Lattice problems in NP ∩ coNP, Journal of the ACM (JACM), v.52 n.5, p.749-765, September 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
	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
	Oded Goldreich , Salil Vadhan, Special Issue On Worst-case Versus Average-case Complexity Editors' Foreword, Computational Complexity, v.16 n.4, p.325-330, December 2007
	Daniele Micciancio, Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions, Computational Complexity, v.16 n.4, p.365-411, December 2007
	Dan Gutfreund , Ronen Shaltiel , Amnon Ta-Shma, If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard Instances, Computational Complexity, v.16 n.4, p.412-441, 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
	Wenbin Chen , Jiangtao Meng, Hardness of approximating the Minimum Solutions of Linear Diophantine Equations, Theoretical Computer Science, v.374 n.1-3, p.191-195, April, 2007
	Andrej Bogdanov , Luca Trevisan, Average-case complexity, Foundations and Trends® in Theoretical Computer Science, v.2 n.1, p.1-106, October 2006
	Dagmar Bruss , Gábor Erdélyi , Tim Meyer , Tobias Riege , Jörg Rothe, Quantum cryptography: A survey, ACM Computing Surveys (CSUR), v.39 n.2, p.6-es, 2007
	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
	Oleg Izmerly , Tal Mor, Chosen ciphertext attacks on lattice-based public key encryption and modern (non-quantum) cryptography in a quantum environment, Theoretical Computer Science, v.367 n.3, p.308-323, December, 2006
	Caroline Fontaine , Fabien Galand, A survey of homomorphic encryption for nonspecialists, European Journal of Information Systems, v.2007 n.1, p.1-15, January 2007
	Simon Blake-Wilson, Information Security, Mathematics, and Public-Key Cryptography, Designs, Codes and Cryptography, v.19 n.2-3, p.77-99, March 2000
	Thomas Plantard , Willy Susilo , Khin Than Win , Qiong Huang, Efficient lattice-based signature scheme, International Journal of Applied Cryptography, v.1 n.2, p.120-132, November 2008
	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
	Chris Peikert , Brent Waters, Lossy trapdoor functions and their applications, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Craig Gentry , Chris Peikert , Vinod Vaikuntanathan, Trapdoors for hard lattices and new cryptographic constructions, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Adam R. Klivans , Alexander A. Sherstov, Cryptographic hardness for learning intersections of halfspaces, Journal of Computer and System Sciences, v.75 n.1, p.2-12, January, 2009
	Shingo Hasegawa , Hiroyuki Hatanaka , Shuji Isobe , Eisuke Koizumi , Hiroki Shizuya, Making Cryptographic Primitives Harder, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, v.E91-A n.1, p.330-337, January 2008
	Ray A. Perlner , David A. Cooper, Quantum resistant public key cryptography: a survey, Proceedings of the 8th Symposium on Identity and Trust on the Internet, April 14-16, 2009, Gaithersburg, Maryland
	Chris Peikert, Public-key cryptosystems from the worst-case shortest vector problem: extended abstract, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA
	Craig Gentry, Fully homomorphic encryption using ideal lattices, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA