zbMATH — the first resource for mathematics

Generating shorter bases for hard random lattices. (English) Zbl 1217.94092
Summary: We revisit the problem of generating a ‘hard’ random lattice together with a basis of relatively short vectors. This problem has gained in importance lately due to new cryptographic schemes that use such a procedure to generate public/secret key pairs. In these applications, a shorter basis corresponds to milder underlying complexity assumptions and smaller key sizes.
The contributions of this work are twofold. First, we simplify and modularize an approach originally due to M. Ajtai [Lect. Notes Comput. Sci. 1644, 1–9 (1999; Zbl 0987.94021)]. Second, we improve the construction and its analysis in several ways, most notably by making the output basis asymptotically as short as possible.

94A60 Cryptography
11H06 Lattices and convex bodies (number-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI
[1] Ajtai, M.: Generating hard instances of the short basis problem. In: ICALP, pp. 1–9 (1999) · Zbl 0987.94021
[2] Ajtai, M.: Generating hard instances of lattice problems. Quad. Mat. 13, 1–32 (2004). Preliminary version in STOC 1996
[3] Cash, D., Hofheinz, D., Kiltz, E., Peikert, C.: Bonsai trees, or how to delegate a lattice basis. In: EUROCRYPT, pp. 523–552 (2010) · Zbl 1280.94043
[4] Goldreich, O., Goldwasser, S., Halevi, S.: Collision-free hashing from lattice problems. Electron. Colloq. Comput. Complex. (ECCC) 3(42) (1996) · Zbl 1343.94055
[5] Goldreich, O., Goldwasser, S., Halevi, S.: Public-key cryptosystems from lattice reduction problems. In: CRYPTO, pp. 112–131 (1997) · Zbl 0889.94011
[6] Gentry, C., Halevi, S., Vaikuntanathan, V.: A simple BGN-type cryptosystem from LWE. In: EUROCRYPT, pp. 506–522 (2010) · Zbl 1280.94060
[7] Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: STOC, pp. 197–206 (2008) · Zbl 1231.68124
[8] Håstad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. SIAM J. Comput. 28(4), 1364–1396 (1999) · Zbl 0940.68048 · doi:10.1137/S0097539793244708
[9] Mazo, J.E., Odlyzko, A.M.: Lattice points in high-dimensional spheres. Mon. Math. 110(1), 47–61 (1990) · Zbl 0719.11063 · doi:10.1007/BF01571276
[10] Micciancio, D.: Improving lattice based cryptosystems using the Hermite normal form. In: CaLC, pp. 126–145 (2001) · Zbl 1006.94529
[11] Micciancio, D., Regev, O.: Worst-case to average-case reductions based on Gaussian measures. SIAM J. Comput. 37(1), 267–302 (2007). Preliminary version in FOCS 2004 · Zbl 1142.68037 · doi:10.1137/S0097539705447360
[12] Micciancio, D., Regev, O.: Lattice-based cryptography. In: Post Quantum Cryptography, pp. 147–191. Springer, Berlin (2009) · Zbl 1161.81324
[13] Micciancio, D., Vadhan, S.P.: Statistical zero-knowledge proofs with efficient provers: Lattice problems and more. In: CRYPTO, pp. 282–298 (2003) · Zbl 1122.68448
[14] Micciancio, D., Warinschi, B.: A linear space algorithm for computing the Hermite normal form. In: ISSAC, pp. 231–236 (2001) · Zbl 1356.68288
[15] Nguyen, P.Q.: Cryptanalysis of the Goldreich-Goldwasser-Halevi cryptosystem from Crypto ’97. In: CRYPTO, pp. 288–304 (1999) · Zbl 1038.94543
[16] Nguyen, P.Q., Regev, O.: Learning a parallelepiped: Cryptanalysis of GGH and NTRU signatures. J. Cryptol. 22(2), 139–160 (2009). Preliminary version in Eurocrypt 2006 · Zbl 1159.94369 · doi:10.1007/s00145-008-9031-0
[17] Peikert, C.: Public-key cryptosystems from the worst-case shortest vector problem. In: STOC, pp. 333–342 (2009) · Zbl 1304.94079
[18] Peikert, C., Vaikuntanathan, V.: Noninteractive statistical zero-knowledge proofs for lattice problems. In: CRYPTO, pp. 536–553 (2008) · Zbl 1183.94045
[19] Peikert, C., Vaikuntanathan, V., Waters, B.: A framework for efficient and composable oblivious transfer. In: CRYPTO, pp. 554–571 (2008) · Zbl 1183.94046
[20] Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6) (2009). Preliminary version in STOC 2005 · Zbl 1192.94106
[21] Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997) · Zbl 1005.11065 · doi:10.1137/S0097539795293172
[22] Vershynin, R.: Lecture notes on non-asymptotic theory of random matrices (2007). Available at http://www-personal.umich.edu/\(\sim\)romanv/teaching/2006-07/280/ , last accessed 17 Feb. 2010
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.