Abstract
In Crypto 1997, Goldreich, Goldwasser and Halevi (GGH) proposed a lattice analogue of McEliece public key cryptosystem, which security is related to the hardness of approximating the closest vector problem (CVP) in a lattice. Furthermore, they also described how to use the same principle of their encryption scheme to provide a signature scheme. Practically, this cryptosystem uses the euclidean norm, l 2-norm, which has been used in many algorithms based on lattice theory. Nonetheless, many drawbacks have been studied and these could lead to cryptanalysis of the scheme. In this paper, we present a novel method of reducing a vector under the l ∞ -norm and propose a digital signature scheme based on it. Our scheme takes advantage of the l ∞ -norm to increase the resistance of the GGH scheme and to decrease the signature length. Furthermore, after some other improvements, we obtain a very efficient signature scheme, that trades the security level, speed and space.
This work is supported by ARC Discovery Grant DP0663306.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Agrell, E., Eriksson, T., Vardy, A., Zeger, K.: Closest point search in lattices. IEEE Transactions on Information Theory 48(8), 2201–2214 (2002)
Ajtai, M.: The shortest vector problem in \(l_{\mbox{2}}\) is NP-hard for randomized reductions. In: 13th Annual ACM Symp. on the Theory of Computing, pp. 10–19 (1998)
Ajtai, M., Dwork, C.: A public-key cryptosystem with worst-case/average-case equivalence. In: 29th Annual ACM Symp. on the Th. of Comp., pp. 284–293 (1997)
Ajtai, M., Kumar, R., Sivakumar, D.: A sieve algorithm for the shortest lattice vector problem. In: 33rd Annual ACM Symp. on Th. of Comp., pp. 601–610 (2001)
Ajtai, M., Kumar, R., Sivakumar, D.: Sampling short lattice vectors and the closest lattice vector problem. In: IEEE CCC, pp. 53–57 (2002)
Babai, L.: On Lovász’ lattice reduction and the nearest lattice point problem. Combinatorica 6(1), 1–13 (1986)
Bajard, J.-C., Imbert, L., Plantard, T.: Modular number systems: Beyond the Mersenne family. In: Handschuh, H., Hasan, M.A. (eds.) SAC 2004. LNCS, vol. 3357, pp. 159–169. Springer, Heidelberg (2004)
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)
Boas, P.V.E.: Another NP-complete problem and the complexity of computing short vectors in lattices. TR 81-04, Math. Dept., Univ. of Amsterdam (1981)
Cai, J.-Y.: Some recent progress on the complexity of lattice problems. In: 14th Annual IEEE Conference on Computational Complexity, pp. 158–178 (1999)
Cassels, J.W.S.: An Introduction to The Geometry of Numbers. Springer, Heidelberg (1959)
Chen, W., Meng, J.: The hardness of the closest vector problem with preprocessing over ℓ ∞ norm. IEEE Trans on Inf Theory 52(10), 4603–4606 (2006)
Cohen, H.: A course in computational algebraic number theory. Graduate Texts in Mathematics, vol. 138. Springer, Heidelberg (1993)
Collatz, L.: Functional Analysis and Numerical Mathematics. Academic Press Inc., U.S. (1966)
Conway, J.H., Sloane, N.J.A.: Sphere Packings, Lattices and Groups. Springer, Heidelberg (1988)
Dinur, I.: Approximating SVP ∞ to within almost-polynomial factors is NP-Hard. In: Bongiovanni, G., Petreschi, R., Gambosi, G. (eds.) CIAC 2000. LNCS, vol. 1767, pp. 263–276. Springer, Heidelberg (2000)
Dinur, I., Kindler, G., Safra, S.: Approximating CVP to within almost polynomial factor is NP-hard. In: FOCS 1998, pp. 99–111 (1998)
Geman, S.: The spectral radius of large random matrices. The Annals of Probability 14(4), 1318–1328 (1986)
Gentry, C., Szydlo, M.: Cryptanalysis of the revised NTRU signature scheme. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 299–320. Springer, Heidelberg (2002)
Goldreich, O., Goldwasser, S.: On the limits of non-approximability of lattice problems. In: the 30th Annual ACM Symp on Th of Computing, pp. 1–9 (1998)
Goldreich, O., Goldwasser, S., Halevi, S.: Public-key cryptosystems from lattice reductions problems. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 112–131. Springer, Heidelberg (1997)
Goldreich, O., Micciancio, D., Safra, S., Seifert, J.-P.: Approximating shortest lattice vectors is not harder than approximating closest lattice vectors. Information Processing Letters 71(2), 55–61 (1999)
Golub, G.H., Loan, C.F.V.: Matrix Computations. The Johns Hopkins University Press (1983)
Hanrot, G., Stehle, D.: Improved analysis of Kannan’s shortest lattice vector algorithm. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, Springer, Heidelberg (2007)
Haviv, I., Regev, O.: Tensor-based hardness of the shortest vector problem to within almost polynomial factors. In: Thirty-nineth annual ACM symposium on Theory of computing, pp. 469–477 (2007)
Helfrich, B.: Algorithms to construct Minkowski reduced an Hermite reduced lattice bases. Theoretical Computer Science 41, 125–139 (1985)
Higham, N.J.: Estimating the matrix p-norm. Numerische Mathematik 62, 539–556 (1992)
Hoffstein, J., Howgrave-Graham, N., Pipher, J., Silverman, J.H., Whyte, W.: NTRUSign: Digital signatures using the NTRU lattice. In: Joye, M. (ed.) CT-RSA 2003. LNCS, vol. 2612, pp. 122–140. Springer, Heidelberg (2003)
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)
Householder, A.S.: The theory of matrices in numerical analysis. Blaisdell Pub. Co., New York (1964)
Kannan, R.: Improved algorithms for integer programming and related lattice problems. In: Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, Boston, Massachusetts, April 1983, pp. 193–206 (1983)
Kannan, R., Bachem, A.: Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix. SIAM J. of Comp 8(4), 499–507 (1979)
Khot, S.: Hardness of approximating the shortest vector problem in high l p norms. In: The 44th Annual IEEE Symposium on FOCS, pp. 290–297 (2003)
Krasnosel’Skii, M.A., Vainikkov, G.M., Zabreiko, P.P., Rutitskii, Y.B., Stetsenko, V.Y.: Approximate solution of operator equations (1972)
Lenstra, A.K., Lenstra, H.W., Lovász, L.: Factoring polynomials with rational coefficients. Mathematische Annalen 261, 513–534 (1982)
Lovász, L.: An Algorithmic Theory of Numbers, Graphs and Convexity. In: CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 50, SIAM Publications, Philadelphia (1986)
McEliece, R.J.: A public-key cryptosystem based on algebraic coding theory. Deep Space Network Progress Report 44, 114–116 (1978)
Micciancio, D.: Improving lattice based cryptosystems using the Hermite normal form. In: Silverman, J.H. (ed.) CaLC 2001. LNCS, vol. 2146, pp. 126–145. Springer, Heidelberg (2001)
Micciancio, D., Warinschi, B.: A linear space algorithm for computing the Hermite normal form. In: Intl. Symp. on Symb. Alg. Comp., pp. 231–236 (2001)
Minkowski, H.: Geometrie der Zahlen. B.G. Teubner, Leipzig (1896)
Nguyen, P.Q.: Cryptanalysis of the Goldreich-Goldwasser-Halevi cryptosystem from crypto 1997. In: Wiener, M.J. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 288–304. Springer, Heidelberg (1999)
Nguyen, P.Q., Regev, O.: Learning a parallelepiped: Cryptanalysis of GGH and NTRU signatures. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 271–288. Springer, Heidelberg (2006)
Nguyen, P.Q., Stehlé, D.: Floating-point LLL revisited. In: Cramer, R.J.F. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 215–233. Springer, Heidelberg (2005)
Nguyen, P.Q., Stehlé, D.: LLL on the average. In: Hess, F., Pauli, S., Pohst, M. (eds.) ANTS 2006. LNCS, vol. 4076, pp. 238–256. Springer, Heidelberg (2006)
Nguyen, P.Q., Stern, J.: The two faces of lattices in cryptology. In: Silverman, J.H. (ed.) CaLC 2001. LNCS, vol. 2146, pp. 146–180. Springer, Heidelberg (2001)
Peikert, C.: Limits on the hardness of lattice problems in ℓ p norms. In: Twenty-Second Annual IEEE Conference on Computational Complexity, pp. 333–346 (2007)
Regev, O.: Lattice-based cryptography. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 131–141. Springer, Heidelberg (2006)
Regev, O., Rosen, R.: Lattice problems and norm embeddings. In: Thirty-eighth annual ACM symposium on Theory of computing, pp. 447–456 (2006)
Schnorr, C.-P.: A hierarchy of polynomial time lattice basis reduction algorithms. Theoretical Computer Science 53(2–3), 201–224 (1987)
Schnorr, C.-P.: A more efficient algorithm for lattice basis reduction. Journal of Algorithms 9(1), 47–62 (1988)
Schnorr, C.-P.: Block Korkin-Zolotarev bases and successive minima (1996)
Schnorr, C.-P.: Fast LLL-type lattice reduction. Information and Computation 204(1), 1–25 (2006)
Szydlo, M.: Hypercubic lattice reduction and analysis of GGH and NTRU signatures. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 433–448. Springer, Heidelberg (2003)
Varga, R.S.: Matrix Iterative Analysis. Prentice-Hall, Englewood Cliffs (1962)
Wilkinson, J.H.: The algebraic eigenvalue problem. Oxford University Press, Inc., New York (1965)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Plantard, T., Susilo, W., Win, K.T. (2008). A Digital Signature Scheme Based on CVP ∞ . In: Cramer, R. (eds) Public Key Cryptography – PKC 2008. PKC 2008. Lecture Notes in Computer Science, vol 4939. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-78440-1_17
Download citation
DOI: https://doi.org/10.1007/978-3-540-78440-1_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-78439-5
Online ISBN: 978-3-540-78440-1
eBook Packages: Computer ScienceComputer Science (R0)