×

Cryptographic functions from worst-case complexity assumptions. (English) Zbl 1191.94098

Nguyen, Phong Q. (ed.) et al., The LLL algorithm. Survey and applications. Dordrecht: Springer (ISBN 978-3-642-02294-4/hbk; 978-3-642-02295-1/ebook). Information Security and Cryptography, 427-452 (2010).
Summary: Lattice problems have been suggested as a potential source of computational hardness to be used in the construction of cryptographic functions that are provably hard to break. A remarkable feature of lattice-based cryptographic functions is that they can be proved secure (that is, hard to break on the average) based on the assumption that the underlying lattice problems are computationally hard in the worst-case. In this paper we give a survey of the constructions and proof techniques used in this area, explain the importance of basing cryptographic functions on the worst-case complexity of lattice problems, and discuss how this affects the traditional approach to cryptanalysis based on random challenges.
For the entire collection see [Zbl 1179.11003].

MSC:

94A60 Cryptography

Software:

SWIFFT
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Lenstra, A. K.; Lenstra, H. W.; Lovász, L., Factoring polynomials with rational coefficients, Mathematische Annalen, 261, 513-534 (1982) · Zbl 0488.12001
[2] Brickell, E.F., Odlyzko, A.M.: Cryptanalysis: A survey of recent results. In: G.J. Simmons (ed.) Contemporary Cryptology, chap. 10, pp. 501-540. IEEE Press (1991)
[3] Joux, A.; Stern, J., Lattice reduction: A toolbox for the cryptanalyst, Journal of Cryptology, 11, 3, 161-185 (1998) · Zbl 0919.94011 · doi:10.1007/s001459900042
[4] Nguyen, P., Stern, J.: The two faces of lattices in cryptology. In: Proceedings of CaLC ’01, LNCS, vol. 2146, pp. 146-180. Springer (2001) · Zbl 1006.94531
[5] Schnorr, C. P.; Euchner, M., Lattice basis reduction: Improved practical algorithms and solving subset sum problems, Mathematical programming, 66, 1-3, 181-199 (1994) · Zbl 0829.90099
[6] Schnorr, CP, A hierarchy of polynomial time lattice basis reduction algorithms, Theoretical Computer Science, 53, 2-3, 201-224 (1987) · Zbl 0642.10030 · doi:10.1016/0304-3975(87)90064-8
[7] Schnorr, CP, A more efficient algorithm for lattice basis reduction, Journal of Algorithms, 9, 1, 47-62 (1988) · Zbl 0825.11015 · doi:10.1016/0196-6774(88)90004-1
[8] Schnorr, CP, Fast LLL-type lattice reduction, Information and Computation, 204, 1, 1-25 (2006) · Zbl 1108.11090 · doi:10.1016/j.ic.2005.04.004
[9] Ajtai, M., Kumar, R., Sivakumar, D.: A sieve algorithm for the shortest lattice vector problem. In: Proceedings of STOC ’01, pp. 266-275. ACM (2001) · Zbl 1323.68561
[10] Kumar, R.; Sivakumar, D., On polynomial-factor approximations to the shortest lattice vector length, SIAM Journal on Discrete Mathematics, 16, 3, 422-425 (2003) · Zbl 1040.11096 · doi:10.1137/S0895480100379981
[11] Nguyen, P., Stehlé, D.: Floating-point LLL revisited. In: Proceedings of EUROCRYPT ’05, LNCS, vol. 3494, pp. 215-233. Springer (2005) · Zbl 1137.94353
[12] Gama, N., Nguyen, P.Q.: Finding short lattice vectors within mordell’s inequality. In: Proceedings of STOC ’08, pp. 207-216. ACM (2008) · Zbl 1230.11153
[13] Ajtai, M.: Generating hard instances of lattice problems. Complexity of Computations and Proofs, Quaderni di Matematica 13, 1-32 (2004). Preliminary version in STOC 1996 · Zbl 1071.11041
[14] Cai, J.Y., Nerurkar, A.P.: An improved worst-case to average-case connection for lattice problems (extended abstract). In: Proceedings of FOCS ’97, pp. 468-477. IEEE (1997)
[15] Micciancio, D., Almost perfect lattices, the covering radius problem, and applications to Ajtai’s connection factor, SIAM Journal on Computing, 34, 1, 118-169 (2004) · Zbl 1112.68067
[16] Micciancio, D.; Regev, O., Worst-case to average-case reductions based on Gaussian measure, SIAM Journal on Computing, 37, 1, 267-302 (2007) · Zbl 1142.68037
[17] Micciancio, D., Generalized compact knapsacks, cyclic lattices, and efficient one-way functions, Computational Complexity, 16, 4, 365-411 (2007) · Zbl 1133.68024
[18] Ajtai, M.: Representing hard lattices with O(n log n) bits. In: Proceedings of STOC ’05,pp. 94-103. ACM (2005) · Zbl 1192.94087
[19] Lyubashevsky, V., Micciancio, D.: Generalized compact knapsacks are collision resistant. In: Proceedings of ICALP ’06, LNCS, vol. 4052, pp. 144-155. Springer (2006) · Zbl 1133.68353
[20] Peikert, C., Rosen, A.: Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices. In: Proceedings of TCC ’06, LNCS, vol. 3876, pp. 145-166. Springer (2006) · Zbl 1112.94020
[21] Lyubashevsky, V., Micciancio, D., Peikert, C., Rosen, A.: Swifft: a modest proposal for fft hashing. In: Proceedings of FSE ’08, LNCS, vol. 5086, pp. 54-72. Springer (2008) · Zbl 1154.68403
[22] Ajtai, M., Dwork, C.: A public-key cryptosystem with worst-case/average-case equivalence. In: Proceedings of STOC ’97, pp. 284-293. ACM (1997) · Zbl 0962.68055
[23] Regev, O., New lattice based cryptographic constructions, Journal of the ACM, 51, 6, 899-942 (2004) · Zbl 1125.94026
[24] Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Proceedings of STOC ’05, pp. 84-93. ACM (2005) · Zbl 1192.94106
[25] Peikert, C., Waters, B.: Lossy trapdoor functions and their applications. In: Proceedings of STOC ’08, pp. 187-196. ACM (2008) · Zbl 1228.94027
[26] Micciancio, D., Vadhan, S.: Statistical zero-knowledge proofs with efficient provers: lattice problems and more. In: Proceedings of CRYPTO ’03, LNCS, vol. 2729, pp. 282-298. Springer (2003) · Zbl 1122.68448
[27] Lyubashevsky, V.: Lattice-based identification schemes secure under active attacks. In: Proceedings of PKC ’08, no. 4939 in LNCS, pp. 162-179. Springer (2008) · Zbl 1162.94388
[28] Lyubashevsky, V., Micciancio, D.: Asymptotically efficient lattice-based digital signatures. In: Proceedings of TCC ’08, LNCS, vol. 4948, pp. 37-54. Springer (2008) · Zbl 1162.94389
[29] Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Proceedings of STOC ’08, pp. 197-206. ACM (2008) · Zbl 1231.68124
[30] Peikert, C., Vaikuntanathan, V.: Noninteractive statistical zero-knowledge proofs for lattice problems. In: Proceedings of CRYPTO ’08, LNCS, vol. 5157, pp. 536-553. Springer (2008) · Zbl 1183.94045
[31] Peikert, C., Vaikuntanathan, V., Waters, B.: A framework for efficient and composable oblivious transfer. In: Proceedings of CRYPTO ’08, LNCS, vol. 5157, pp. 554-571. Springer (2008) · Zbl 1183.94046
[32] Regev, O.: On the complexity of lattice problems with polynomial approximation factors. In: this volume (2008) · Zbl 1237.68102
[33] Micciancio, D., Goldwasser, S.: Complexity of Lattice Problems: a cryptographic perspective, The Kluwer International Series in Engineering and Computer Science, vol. 671. Kluwer Academic Publishers (2002) · Zbl 1140.94010
[34] Goldreich, O.; Micciancio, D.; Safra, S.; Seifert, JP, Approximating shortest lattice vectors is not harder than approximating closest lattice vectors, Information Processing Letters, 71, 2, 55-61 (1999) · Zbl 0999.68085 · doi:10.1016/S0020-0190(99)00083-6
[35] Babai, L., On Lovasz’ lattice reduction and the nearest lattice point problem, Combinatorica, 6, 1, 1-13 (1986) · Zbl 0593.68030 · doi:10.1007/BF02579403
[36] Ajtai, M.: The worst-case behavior of Schnorr’s algorithm approximating the shortest nonzero vector in a lattice. In: Proceedings of STOC ’03, pp. 396-406. ACM (2003) · Zbl 1192.68336
[37] Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: a ring based public key cryptosystem. In: Proceedings of ANTS-III, LNCS, vol. 1423, pp. 267-288. Springer (1998) · Zbl 1067.94538
[38] Goldwasser, S., Micali, S.: Probabilistic encryption. Journal of Computer and System Sciences 28(2), 270-299 (1984). Preliminary version in Proc. of STOC 1982 · Zbl 0563.94013
[39] Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: Proceedings of STOC ’89, pp. 44-61. ACM (1989) · Zbl 0718.68042
[40] Cai, JY, A relation of primal-dual lattices and the complexity of the shortest lattice vector problem, Theoretical Computer Science, 207, 1, 105-116 (1998) · Zbl 0926.11047 · doi:10.1016/S0304-3975(98)00058-9
[41] Goldreich, O., Goldwasser, S., Halevi, S.: Eliminating decryption errors in the Ajtai-Dwork cryptosystem. In: Proceedings of CRYPTO ’97, LNCS, vol. 1294, pp. 105-111. Springer (1997) · Zbl 0889.94010
[42] Nguyen, P., Stehlé, D.: LLL on the average. In: Proceedings of ANTS-VII, LNCS, vol. 4076, pp. 238-256. Springer (2006) · Zbl 1143.11357
[43] Gama, N., Nguyen, P.Q.: Predicting lattice reduction. In: Proceedings of EUROCRYPT ’08, LNCS, vol. 4965, pp. 31-51. Springer (2008) · Zbl 1149.94314
[44] Schnorr, C.P., Hörner, H.H.: Attacking the Chor-Rivest cryptosystem by improved lattice reduction. In: Proceedings of EUROCRYPT ’95, LNCS, vol. 921, pp. 1-12. Springer (1995) · Zbl 0973.94514
[45] Lenstra, AK; Verheul, ER, Selecting cryptographic key sizes, Journal of Cryptology, 14, 4, 255-293 (2001) · Zbl 1006.94020
[46] Nguyen, P., Stern, J.: Cryptanalysis of the Ajtai-Dwork cryptosystem. In: Proceedings of CRYPTO ’98, LNCS, vol. 1462, pp. 223-242. Springer (1998) · Zbl 0984.94508
[47] Dinur, I., Approximating SVP_∞ to within almost-polynomial factors is NP-hard, Theoretical Computer Science, 285, 1, 55-71 (2002) · Zbl 1016.68041 · doi:10.1016/S0304-3975(01)00290-0
[48] Regev, O., Rosen, R.: Lattice problems and norm embeddings. In: Proceedings of STOC ’06, pp. 447-456. ACM (2006) · Zbl 1301.68151
[49] Haviv, I., Regev, O.: Tensor-based hardness of the shortest vector problem to within almost polynomial factors. In: Proceedings of STOC ’07, pp. 469-477. ACM (2007) · Zbl 1232.68066
[50] Lovász, L.; Scarf, H., The generalized basis reduction algorithm, Mathematics of Operations Research, 17, 3, 754-764 (1992) · Zbl 0774.90060 · doi:10.1287/moor.17.3.751
[51] Gama, N., Howgrave-Graham, N., Nguyen, P.: Symplectic lattice reduction and NTRU. In: Proceedings of EUROCRYPT ’06, LNCS, vol. 4004, pp. 233-253. Springer (2006) · Zbl 1140.94339
[52] Lyubashevsy, V., Micciancio, D., Peikert, C., Rosen, A.: Provably secure FFT hashing. In: 2nd NIST cryptographic hash workshop. Santa Barbara, CA, USA (2006)
[53] Ajtai, M.: Random lattices and a conjectured 0-1 law about their polynomial time computable properties. In: Proceedings of FOCS ’02, pp. 733-742. IEEE (2002)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.