{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T21:22:51Z","timestamp":1751923371766},"publisher-location":"Berlin, Heidelberg","reference-count":55,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540784395"},{"type":"electronic","value":"9783540784401"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-78440-1_17","type":"book-chapter","created":{"date-parts":[[2008,2,26]],"date-time":"2008-02-26T10:53:32Z","timestamp":1204023212000},"page":"288-307","source":"Crossref","is-referenced-by-count":12,"title":["A Digital Signature Scheme Based on CVP \u2009\u221e"],"prefix":"10.1007","author":[{"given":"Thomas","family":"Plantard","sequence":"first","affiliation":[]},{"given":"Willy","family":"Susilo","sequence":"additional","affiliation":[]},{"given":"Khin Than","family":"Win","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"8","key":"17_CR1","doi-asserted-by":"publisher","first-page":"2201","DOI":"10.1109\/TIT.2002.800499","volume":"48","author":"E. Agrell","year":"2002","unstructured":"Agrell, E., Eriksson, T., Vardy, A., Zeger, K.: Closest point search in lattices. IEEE Transactions on Information Theory\u00a048(8), 2201\u20132214 (2002)","journal-title":"IEEE Transactions on Information Theory"},{"key":"17_CR2","doi-asserted-by":"crossref","unstructured":"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\u201319 (1998)","DOI":"10.1145\/276698.276705"},{"key":"17_CR3","doi-asserted-by":"crossref","unstructured":"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\u2013293 (1997)","DOI":"10.1145\/258533.258604"},{"key":"17_CR4","doi-asserted-by":"crossref","unstructured":"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\u2013610 (2001)","DOI":"10.1145\/380752.380857"},{"key":"17_CR5","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Kumar, R., Sivakumar, D.: Sampling short lattice vectors and the closest lattice vector problem. In: IEEE CCC, pp. 53\u201357 (2002)","DOI":"10.1109\/CCC.2002.1004339"},{"issue":"1","key":"17_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02579403","volume":"6","author":"L. Babai","year":"1986","unstructured":"Babai, L.: On Lov\u00e1sz\u2019 lattice reduction and the nearest lattice point problem. Combinatorica\u00a06(1), 1\u201313 (1986)","journal-title":"Combinatorica"},{"key":"17_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/978-3-540-30564-4_11","volume-title":"Selected Areas in Cryptography","author":"J.-C. Bajard","year":"2004","unstructured":"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.\u00a03357, pp. 159\u2013169. Springer, Heidelberg (2004)"},{"key":"17_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/978-3-540-73420-8_8","volume-title":"Automata, Languages and Programming","author":"J. Bl\u00f6mer","year":"2007","unstructured":"Bl\u00f6mer, J., Naewe, S.: Sampling Methods for Shortest Vectors, Closest Vectors and Successive Minima. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 65\u201377. Springer, Heidelberg (2007)"},{"key":"17_CR9","unstructured":"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)"},{"key":"17_CR10","unstructured":"Cai, J.-Y.: Some recent progress on the complexity of lattice problems. In: 14th Annual IEEE Conference on Computational Complexity, pp. 158\u2013178 (1999)"},{"key":"17_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-62035-5","volume-title":"An Introduction to The Geometry of Numbers","author":"J.W.S. Cassels","year":"1959","unstructured":"Cassels, J.W.S.: An Introduction to The Geometry of Numbers. Springer, Heidelberg (1959)"},{"issue":"10","key":"17_CR12","doi-asserted-by":"publisher","first-page":"4603","DOI":"10.1109\/TIT.2006.881835","volume":"52","author":"W. Chen","year":"2006","unstructured":"Chen, W., Meng, J.: The hardness of the closest vector problem with preprocessing over \u2113\u2009\u221e\u2009 norm. IEEE Trans on Inf Theory\u00a052(10), 4603\u20134606 (2006)","journal-title":"IEEE Trans on Inf Theory"},{"key":"17_CR13","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-02945-9","volume-title":"A course in computational algebraic number theory","author":"H. Cohen","year":"1993","unstructured":"Cohen, H.: A course in computational algebraic number theory. Graduate Texts in Mathematics, vol.\u00a0138. Springer, Heidelberg (1993)"},{"key":"17_CR14","volume-title":"Functional Analysis and Numerical Mathematics","author":"L. Collatz","year":"1966","unstructured":"Collatz, L.: Functional Analysis and Numerical Mathematics. Academic Press Inc., U.S. (1966)"},{"key":"17_CR15","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2016-7","volume-title":"Sphere Packings, Lattices and Groups","author":"J.H. Conway","year":"1988","unstructured":"Conway, J.H., Sloane, N.J.A.: Sphere Packings, Lattices and Groups. Springer, Heidelberg (1988)"},{"key":"17_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/3-540-46521-9_22","volume-title":"Algorithms and Complexity","author":"I. Dinur","year":"2000","unstructured":"Dinur, I.: Approximating SVP\u2009\u221e\u2009 to within almost-polynomial factors is NP-Hard. In: Bongiovanni, G., Petreschi, R., Gambosi, G. (eds.) CIAC 2000. LNCS, vol.\u00a01767, pp. 263\u2013276. Springer, Heidelberg (2000)"},{"key":"17_CR17","doi-asserted-by":"crossref","unstructured":"Dinur, I., Kindler, G., Safra, S.: Approximating CVP to within almost polynomial factor is NP-hard. In: FOCS 1998, pp. 99\u2013111 (1998)","DOI":"10.1109\/SFCS.1998.743433"},{"issue":"4","key":"17_CR18","doi-asserted-by":"publisher","first-page":"1318","DOI":"10.1214\/aop\/1176992372","volume":"14","author":"S. Geman","year":"1986","unstructured":"Geman, S.: The spectral radius of large random matrices. The Annals of Probability\u00a014(4), 1318\u20131328 (1986)","journal-title":"The Annals of Probability"},{"key":"17_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/3-540-46035-7_20","volume-title":"Advances in Cryptology - EUROCRYPT 2002","author":"C. Gentry","year":"2002","unstructured":"Gentry, C., Szydlo, M.: Cryptanalysis of the revised NTRU signature scheme. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol.\u00a02332, pp. 299\u2013320. Springer, Heidelberg (2002)"},{"key":"17_CR20","doi-asserted-by":"crossref","unstructured":"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\u20139 (1998)","DOI":"10.1145\/276698.276704"},{"key":"17_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1007\/BFb0052231","volume-title":"Advances in Cryptology - CRYPTO \u201997","author":"O. Goldreich","year":"1997","unstructured":"Goldreich, O., Goldwasser, S., Halevi, S.: Public-key cryptosystems from lattice reductions problems. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol.\u00a01294, pp. 112\u2013131. Springer, Heidelberg (1997)"},{"issue":"2","key":"17_CR22","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/S0020-0190(99)00083-6","volume":"71","author":"O. Goldreich","year":"1999","unstructured":"Goldreich, O., Micciancio, D., Safra, S., Seifert, J.-P.: Approximating shortest lattice vectors is not harder than approximating closest lattice vectors. Information Processing Letters\u00a071(2), 55\u201361 (1999)","journal-title":"Information Processing Letters"},{"key":"17_CR23","unstructured":"Golub, G.H., Loan, C.F.V.: Matrix Computations. The Johns Hopkins University Press (1983)"},{"key":"17_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74143-5_10","volume-title":"Advances in Cryptology - CRYPTO 2007","author":"G. Hanrot","year":"2007","unstructured":"Hanrot, G., Stehle, D.: Improved analysis of Kannan\u2019s shortest lattice vector algorithm. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol.\u00a04622, Springer, Heidelberg (2007)"},{"key":"17_CR25","doi-asserted-by":"crossref","unstructured":"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\u2013477 (2007)","DOI":"10.1145\/1250790.1250859"},{"key":"17_CR26","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/0304-3975(85)90067-2","volume":"41","author":"B. Helfrich","year":"1985","unstructured":"Helfrich, B.: Algorithms to construct Minkowski reduced an Hermite reduced lattice bases. Theoretical Computer Science\u00a041, 125\u2013139 (1985)","journal-title":"Theoretical Computer Science"},{"key":"17_CR27","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1007\/BF01396242","volume":"62","author":"N.J. Higham","year":"1992","unstructured":"Higham, N.J.: Estimating the matrix p-norm. Numerische Mathematik\u00a062, 539\u2013556 (1992)","journal-title":"Numerische Mathematik"},{"key":"17_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1007\/3-540-36563-X_9","volume-title":"Topics in Cryptology - CT-RSA 2003","author":"J. Hoffstein","year":"2003","unstructured":"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.\u00a02612, pp. 122\u2013140. Springer, Heidelberg (2003)"},{"key":"17_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/BFb0054868","volume-title":"Algorithmic Number Theory","author":"J. Hoffstein","year":"1998","unstructured":"Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: A ring-based public key cryptosystem. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol.\u00a01423, pp. 267\u2013288. Springer, Heidelberg (1998)"},{"key":"17_CR30","volume-title":"The theory of matrices in numerical analysis","author":"A.S. Householder","year":"1964","unstructured":"Householder, A.S.: The theory of matrices in numerical analysis. Blaisdell Pub. Co., New York (1964)"},{"key":"17_CR31","doi-asserted-by":"crossref","unstructured":"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\u2013206 (1983)","DOI":"10.1145\/800061.808749"},{"issue":"4","key":"17_CR32","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1137\/0208040","volume":"8","author":"R. Kannan","year":"1979","unstructured":"Kannan, R., Bachem, A.: Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix. SIAM J. of Comp\u00a08(4), 499\u2013507 (1979)","journal-title":"SIAM J. of Comp"},{"key":"17_CR33","doi-asserted-by":"crossref","unstructured":"Khot, S.: Hardness of approximating the shortest vector problem in high l p norms. In: The 44th Annual IEEE Symposium on FOCS, pp. 290\u2013297 (2003)","DOI":"10.1109\/SFCS.2003.1238203"},{"key":"17_CR34","doi-asserted-by":"crossref","unstructured":"Krasnosel\u2019Skii, M.A., Vainikkov, G.M., Zabreiko, P.P., Rutitskii, Y.B., Stetsenko, V.Y.: Approximate solution of operator equations (1972)","DOI":"10.1007\/978-94-010-2715-1"},{"key":"17_CR35","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1007\/BF01457454","volume":"261","author":"A.K. Lenstra","year":"1982","unstructured":"Lenstra, A.K., Lenstra, H.W., Lov\u00e1sz, L.: Factoring polynomials with rational coefficients. Mathematische Annalen\u00a0261, 513\u2013534 (1982)","journal-title":"Mathematische Annalen"},{"key":"17_CR36","volume-title":"CBMS-NSF Regional Conference Series in Applied Mathematics","author":"L. Lov\u00e1sz","year":"1986","unstructured":"Lov\u00e1sz, L.: An Algorithmic Theory of Numbers, Graphs and Convexity. In: CBMS-NSF Regional Conference Series in Applied Mathematics, vol.\u00a050, SIAM Publications, Philadelphia (1986)"},{"key":"17_CR37","first-page":"114","volume":"44","author":"R.J. McEliece","year":"1978","unstructured":"McEliece, R.J.: A public-key cryptosystem based on algebraic coding theory. Deep Space Network Progress Report\u00a044, 114\u2013116 (1978)","journal-title":"Deep Space Network Progress Report"},{"key":"17_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1007\/3-540-44670-2_11","volume-title":"Cryptography and Lattices","author":"D. Micciancio","year":"2001","unstructured":"Micciancio, D.: Improving lattice based cryptosystems using the Hermite normal form. In: Silverman, J.H. (ed.) CaLC 2001. LNCS, vol.\u00a02146, pp. 126\u2013145. Springer, Heidelberg (2001)"},{"key":"17_CR39","doi-asserted-by":"crossref","unstructured":"Micciancio, D., Warinschi, B.: A linear space algorithm for computing the Hermite normal form. In: Intl. Symp. on Symb. Alg. Comp., pp. 231\u2013236 (2001)","DOI":"10.1145\/384101.384133"},{"key":"17_CR40","volume-title":"Geometrie der Zahlen","author":"H. Minkowski","year":"1896","unstructured":"Minkowski, H.: Geometrie der Zahlen. B.G. Teubner, Leipzig (1896)"},{"key":"17_CR41","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1007\/3-540-48405-1_18","volume-title":"Advances in Cryptology - CRYPTO \u201999","author":"P.Q. Nguyen","year":"1999","unstructured":"Nguyen, P.Q.: Cryptanalysis of the Goldreich-Goldwasser-Halevi cryptosystem from crypto 1997. In: Wiener, M.J. (ed.) CRYPTO 1999. LNCS, vol.\u00a01666, pp. 288\u2013304. Springer, Heidelberg (1999)"},{"key":"17_CR42","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/11761679_17","volume-title":"Advances in Cryptology - EUROCRYPT 2006","author":"P.Q. Nguyen","year":"2006","unstructured":"Nguyen, P.Q., Regev, O.: Learning a parallelepiped: Cryptanalysis of GGH and NTRU signatures. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol.\u00a04004, pp. 271\u2013288. Springer, Heidelberg (2006)"},{"key":"17_CR43","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/11426639_13","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2005","author":"P.Q. Nguyen","year":"2005","unstructured":"Nguyen, P.Q., Stehl\u00e9, D.: Floating-point LLL revisited. In: Cramer, R.J.F. (ed.) EUROCRYPT 2005. LNCS, vol.\u00a03494, pp. 215\u2013233. Springer, Heidelberg (2005)"},{"key":"17_CR44","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/11792086_18","volume-title":"Algorithmic Number Theory","author":"P.Q. Nguyen","year":"2006","unstructured":"Nguyen, P.Q., Stehl\u00e9, D.: LLL on the average. In: Hess, F., Pauli, S., Pohst, M. (eds.) ANTS 2006. LNCS, vol.\u00a04076, pp. 238\u2013256. Springer, Heidelberg (2006)"},{"key":"17_CR45","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1007\/3-540-44670-2_12","volume-title":"Cryptography and Lattices","author":"P.Q. Nguyen","year":"2001","unstructured":"Nguyen, P.Q., Stern, J.: The two faces of lattices in cryptology. In: Silverman, J.H. (ed.) CaLC 2001. LNCS, vol.\u00a02146, pp. 146\u2013180. Springer, Heidelberg (2001)"},{"key":"17_CR46","doi-asserted-by":"crossref","unstructured":"Peikert, C.: Limits on the hardness of lattice problems in \u2113 p norms. In: Twenty-Second Annual IEEE Conference on Computational Complexity, pp. 333\u2013346 (2007)","DOI":"10.1109\/CCC.2007.12"},{"key":"17_CR47","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/11818175_8","volume-title":"Advances in Cryptology - CRYPTO 2006","author":"O. Regev","year":"2006","unstructured":"Regev, O.: Lattice-based cryptography. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol.\u00a04117, pp. 131\u2013141. Springer, Heidelberg (2006)"},{"key":"17_CR48","doi-asserted-by":"crossref","unstructured":"Regev, O., Rosen, R.: Lattice problems and norm embeddings. In: Thirty-eighth annual ACM symposium on Theory of computing, pp. 447\u2013456 (2006)","DOI":"10.1145\/1132516.1132581"},{"issue":"2\u20133","key":"17_CR49","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/0304-3975(87)90064-8","volume":"53","author":"C.-P. Schnorr","year":"1987","unstructured":"Schnorr, C.-P.: A hierarchy of polynomial time lattice basis reduction algorithms. Theoretical Computer Science\u00a053(2\u20133), 201\u2013224 (1987)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"17_CR50","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0196-6774(88)90004-1","volume":"9","author":"C.-P. Schnorr","year":"1988","unstructured":"Schnorr, C.-P.: A more efficient algorithm for lattice basis reduction. Journal of Algorithms\u00a09(1), 47\u201362 (1988)","journal-title":"Journal of Algorithms"},{"key":"17_CR51","unstructured":"Schnorr, C.-P.: Block Korkin-Zolotarev bases and successive minima (1996)"},{"issue":"1","key":"17_CR52","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ic.2005.04.004","volume":"204","author":"C.-P. Schnorr","year":"2006","unstructured":"Schnorr, C.-P.: Fast LLL-type lattice reduction. Information and Computation\u00a0204(1), 1\u201325 (2006)","journal-title":"Information and Computation"},{"key":"17_CR53","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/3-540-39200-9_27","volume-title":"Advances in Cryptology \u2013 EUROCRPYT 2003","author":"M. Szydlo","year":"2003","unstructured":"Szydlo, M.: Hypercubic lattice reduction and analysis of GGH and NTRU signatures. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol.\u00a02656, pp. 433\u2013448. Springer, Heidelberg (2003)"},{"key":"17_CR54","volume-title":"Matrix Iterative Analysis","author":"R.S. Varga","year":"1962","unstructured":"Varga, R.S.: Matrix Iterative Analysis. Prentice-Hall, Englewood Cliffs (1962)"},{"key":"17_CR55","volume-title":"The algebraic eigenvalue problem","author":"J.H. Wilkinson","year":"1965","unstructured":"Wilkinson, J.H.: The algebraic eigenvalue problem. Oxford University Press, Inc., New York (1965)"}],"container-title":["Lecture Notes in Computer Science","Public Key Cryptography \u2013 PKC 2008"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-78440-1_17.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T11:09:06Z","timestamp":1619521746000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-78440-1_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540784395","9783540784401"],"references-count":55,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-78440-1_17","relation":{},"subject":[]}}