New Variants of Lattice Problems and Their NP-Hardness

1. Ajtai, M.: The shortest vector problem in l 2 is np-hard for randomized reductions. In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, pp. 10–19. ACM (1998)

   Google Scholar 

2. Ajtai, M., Dwork, C.: A public-key cryptosystem with worst-case/average-case equivalence. In: Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing, pp. 284–293. ACM (1997)

   Google Scholar 

3. Ajtai, M., Kumar, R., Sivakumar, D.: A sieve algorithm for the shortest lattice vector problem. In: Proceedings of the Thirty-third Annual ACM Symposium on Theory of Computing, pp. 601–610. ACM (2001)

   Google Scholar 

4. Babai On, L.: lovászlattice reduction and the nearest lattice point problem. Combinatorica 6(1), 1–13 (1986)

   Article  MathSciNet  Google Scholar 

5. Blömer, J., Naewe, S.: Sampling methods for shortest vectors, closest vectors and successive minima. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 65–77. Springer, Heidelberg (2007)

   Chapter  Google Scholar 

6. Cai, J.-Y., Nerurkar, A.: Approximating the svp to within a factor (1+ 1/dim e) is np-hard under randomized reductions. Journal of Computer and System Sciences 59(2), 221–239 (1999)

   Article  MATH  MathSciNet  Google Scholar 

7. Gary, M.R., Johnson, D.S.: Computers and intractability: A guide to the theory of np-completeness (1979)

   Google Scholar 

8. Gentry, C.: Fully homomorphic encryption using ideal lattices (2009)

   Google Scholar 

9. Goldreich, O., Goldwasser, S.: On the limits of non-approximability of lattice problems. In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, pp. 1–9. ACM (1998)

   Google Scholar 

10. Goldreich, O., Goldwasser, S., Halevi, S.: Public-key cryptosystems from lattice reduction problems. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 112–131. Springer, Heidelberg (1997)

    Chapter  Google Scholar 

11. Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: A ring-based public key cryptosystem. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 267–288. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

12. Khot, S.: Hardness of approximating the shortest vector problem in lattices. Journal of the ACM (JACM) 52(5), 789–808 (2005)

    Article  MathSciNet  Google Scholar 

13. Lenstra, A.K., Lenstra, H.W., Lovász, L.: Factoring polynomials with rational coefficients. Mathematische Annalen 261(4), 515–534 (1982)

    Article  MATH  MathSciNet  Google Scholar 

14. Micciancio, D.: The shortest vector in a lattice is hard to approximate to within some constant. SIAM Journal on Computing 30(6), 2008–2035 (2001)

    Article  MATH  MathSciNet  Google Scholar 

15. Micciancio, D.: Inapproximability of the shortest vector problem: Toward a deterministic reduction. Theory of Computing 8(1), 487–512 (2012)

    Article  MathSciNet  Google Scholar 

16. Micciancio, D., Goldwasser, S.: Complexity of lattice problems: a cryptographic perspective, vol. 671. Springer (2002)

    Google Scholar 

17. Micciancio, D., Voulgaris, P.: A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations. In: Proceedings of the 42nd ACM Symposium on Theory of Computing, pp. 351–358. ACM (2010)

    Google Scholar 

18. Minkowski, H.: Geometrie der zahlen. BG Teubner (1910)

    Google Scholar 

19. Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6), 34:1–34:40 (2009)

    Google Scholar 

20. Schnorr, C.-P.: A hierarchy of polynomial time lattice basis reduction algorithms. Theoretical Computer Science 53(2), 201–224 (1987)

    Article  MATH  MathSciNet  Google Scholar 

21. van Emde-Boas, P.: Another NP-complete partition problem and the complexity of computing short vectors in a lattice, Department, Univ. (1981)

    Google Scholar 

22. Voronoï, G.: Nouvelles applications des paramètres continus à la théorie des formes quadratiques. deuxième mémoire. recherches sur les parallélloèdres primitifs. Journal für die reine und angewandte Mathematik 134, 198–287 (1908)

    MATH  Google Scholar 

Download references