On the Limits of Nonapproximability of Lattice Problems

Ajtai, 1996, Generating hard instances of lattice problems Ajtai, 1998, The shortest vector problem in L2 is NP-hard for randomized reductions Ajtai, 1997, A public-key cryptosystem with worst-case/average-case equivalence M. Alekhnovich, On approximating the minimal code distance, private communication, Oct. 1997. Apostol, 1969 Arora, 1997, The hardness of approximate optima in lattices, codes, and systems of linear equations, J. Comput. System Sci., 54, 317, 10.1006/jcss.1997.1472 Babai, 1985, Trading group theory for randomness Babai, 1986, On Lovász lattice reduction and the nearest lattice point problem, Combinatorica, 6, 1, 10.1007/BF02579403 Banaszczyk, 1993, New bounds in some transference theorems in the geometry of numbers, Math. Annal., 296, 625, 10.1007/BF01445125 Bellare, 1993, Randomness in interactive proofs, Comput. Complexity, 4, 319, 10.1007/BF01275487 Blum, 1984, An efficient probabilistic public-key encryption scheme which hides all partial information, 196 Boppana, 1987, Does Co-NP have short interactive proofs?, IPL, 25, 127, 10.1016/0020-0190(87)90232-8 Brassard, 1979, Relativized cryptography Cai, 1998, A relation of primal-dual lattices and the complexity of shortest lattice vector problem, Theoret. Comput. Sci., 207, 105, 10.1016/S0304-3975(98)00058-9 Cai, 1997, An improved worst-case to average-case connection for lattice problems Dyer, 1991, A random polynomial-time algorithm for approximating the volume of convex bodies, J. Assoc. Comput. Mach., 38, 1, 10.1145/102782.102783 Even, 1984, The complexity of promise problems with applications to public-key cryptography, Inform. and Control, 61, 159, 10.1016/S0019-9958(84)80056-X Feige, 1996, A threshold of ln n for approximating set cover Fortnow, 1989, The complexity of perfect zero-knowledge, 5, 327 Fürer, 1989, On completeness and soundness in interactive proof systems, 5, 429 Goldreich, 1998 O. Goldreich, and, S. Goldwasser, On the possibility of basing cryptography on the assumption that P≠NP, manuscript, Feb. 1998. Available as record 98-05 at, http://theory.lcs.mit.edu/∼tcryptol. Goldreich, 1997, Public-key cryptosystems from lattice reduction problems, 1294 Goldreich, 1982, A perfect zero-knowledge proof for a decision problem equivalent to discrete logarithm, J. Cryptology, 6, 77 Goldreich, 1991, Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems, J. Assoc. Comput. Mach., 38, 691, 10.1145/116825.116852 Goldreich, 1998, Honest-verifier statistical zero-knowledge equals general statistical zero-knowledge Goldwasser, 1984, Probabilistic encryption, J. Comput. System Sci., 28, 270, 10.1016/0022-0000(84)90070-9 Goldwasser, 1989, The knowledge complexity of interactive proof systems, SIAM J. Comput., 18, 186, 10.1137/0218012 Goldwasser, 1989, Private coins versus public coins in interactive proof systems, 5, 73 Grollmann, 1988, Complexity measures for public-key cryptosystems, SIAM J. Comput., 17, 309, 10.1137/0217018 Grötschel, 1988 Håstad, 1988, Dual vectors and lower bounds for the nearest lattice point problem, Combinatorica, 8, 75, 10.1007/BF02122554 Håstad, 1997, Getting optimal in-approximability results Kannan, 1987, Algorithmic geometry of numbers R. Kannan, L. Lovász, and, M. Simonovits, Random walks and O*(n5) volume algorithm for convex bodies, Random Struct. Algorithms, in press. Karloff, 1997, A 7/8-eps approximation algorithm for MAX 3SAT? Knuth, 1973 Knuth, 1981 Lagarias, 1990, Korkine–Zolotarev bases and successive minima of a lattice and its reciprocal lattice, Combinatorica, 10, 333, 10.1007/BF02128669 Lenstra, 1982, Factoring polynomials with rational coefficients, Math. Ann., 261, 515, 10.1007/BF01457454 Lenstra, 1983, Integer programming with a fixed number of variables, Math. Oper. Res., 8, 538, 10.1287/moor.8.4.538 D. Micciancio, On the inapproximability of the shortest vector in a lattice within some constant factor, preliminary version MIT/LCS/TM-574, February 1998. Available as TR98-016 at, http://www.eccc.uni-trier.de/eccc/. D. Micciancio, Lattice based cryptography: A global improvement, March 1999, available as record 99-05 at, http://philby.ucsd.edu/cryptolib. Okamoto, 1996, On relationships between statistical zero-knowledge proofs Sahai, 1997, A complete promise problem for statistical zero-knowledge Schnorr, 1987, A hierarchy of polynomial time lattice basis reduction algorithms, Theoret. Comput. Sci., 53, 201, 10.1016/0304-3975(87)90064-8 van Emde Boas, 1981, Report