{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T12:58:54Z","timestamp":1772283534305,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540675174","type":"print"},{"value":"9783540455394","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-45539-6_4","type":"book-chapter","created":{"date-parts":[[2007,7,16]],"date-time":"2007-07-16T12:26:08Z","timestamp":1184588768000},"page":"53-69","source":"Crossref","is-referenced-by-count":43,"title":["Noisy Polynomial Interpolation and Noisy Chinese Remaindering"],"prefix":"10.1007","author":[{"given":"Daniel","family":"Bleichenbacher","sequence":"first","affiliation":[]},{"given":"Phong Q.","family":"Nguyen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2000,5,12]]},"reference":[{"key":"4_CR1","doi-asserted-by":"crossref","unstructured":"M. Ajtai. Generating hard instances of lattice problems. In Proc. of 28th STOC, pages 99\u2013108. ACM, 1996. Available at [11] as TR96-007 report.","DOI":"10.1145\/237814.237838"},{"key":"4_CR2","doi-asserted-by":"crossref","unstructured":"M. Ajtai. The shortest vector problem in L 2 is NP-hard for randomized reductions. In Proc. 30th ACM STOC, 1998. Available at [11] as TR97-047.","DOI":"10.1145\/276698.276705"},{"issue":"2","key":"4_CR3","first-page":"488","volume":"28","author":"S. Ar","year":"1999","unstructured":"S. Ar, R. Lipton, R. Rubinfeld, and M. Sudan. Reconstructing algebraic functions from mixed data. SIAM J. of Computing, 28(2):488\u2013511, 1999.","journal-title":"SIAM J. of Computing"},{"key":"4_CR4","unstructured":"A. O. L. Atkin. The number of points on an elliptic curve modulo a prime. Email on the Number Theory mailing list, 1988."},{"key":"4_CR5","unstructured":"A. O. L. Atkin. The number of points on an elliptic curve modulo a prime. Email on the Number Theory mailing list, 1991."},{"key":"4_CR6","doi-asserted-by":"crossref","unstructured":"D. Boneh. Finding smooth integers in short intervals using CRT decoding. In Proc. of 32nd STOC. ACM, 2000.","DOI":"10.1145\/335305.335337"},{"key":"4_CR7","doi-asserted-by":"crossref","unstructured":"J.H. Conway and N.J.A. Sloane. Sphere Packings, Lattices and Groups. Springer-Verlag, 1998. Third edition.","DOI":"10.1007\/978-1-4757-6568-7"},{"issue":"4","key":"4_CR8","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/s001459900030","volume":"10","author":"D. Coppersmith","year":"1997","unstructured":"D. Coppersmith. Small solutions to polynomial equations, and low exponent RSA vulnerabilities. J. of Cryptology, 10(4):233\u2013260, 1997.","journal-title":"J. of Cryptology"},{"key":"4_CR9","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/BF01201999","volume":"2","author":"M.J. Coster","year":"1992","unstructured":"M.J. Coster, A. Joux, B.A. LaMacchia, A.M. Odlyzko, C.-P. Schnorr, and J. Stern. Improved low-density subset sum algorithms. Comput. Complexity, 2:111\u2013128, 1992.","journal-title":"Comput. Complexity"},{"key":"4_CR10","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1007\/3-540-45539-6_27","volume-title":"Proc. of Eurocrypt 2000","author":"N. Courtois","year":"2000","unstructured":"N. Courtois, A. Klimov, J. Patarin, and A. Shamir. Efficient algorithms for solving overdefined systems of multivariate polynomial equations. In Proc. of Eurocrypt 2000, volume 1807 of LNCS, pages 392\u2013407. Springer-Verlag, 2000."},{"key":"4_CR11","unstructured":"ECCC. http:\/\/www.eccc.uni-trier.de\/eccc\/ . The Electronic Colloquium on Computational Complexity."},{"key":"4_CR12","doi-asserted-by":"crossref","unstructured":"N. D. Elkies. Explicit isogenies. Draft, 1991.","DOI":"10.1155\/S1073792891000144"},{"issue":"4","key":"4_CR13","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/S0167-739X(99)00055-2","volume":"16","author":"C. Ellison","year":"2000","unstructured":"C. Ellison, C. Hall, R. Milbert, and B. Schneier. Protecting secret keys with personal entropy. Future Generation Computer Systems, 16(4):311\u2013318, 2000. Available at http:\/\/www.counterpane.com\/ .","journal-title":"Future Generation Computer Systems"},{"key":"4_CR14","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1007\/3-540-48405-1_8","volume-title":"Proc. of Crypto\u2019 99","author":"N. Gilboa","year":"1999","unstructured":"N. Gilboa. Two party RSA key generation. In Proc. of Crypto\u2019 99, volume 1666 of LNCS, pages 116\u2013129. Springer-Verlag, 1999."},{"key":"4_CR15","doi-asserted-by":"crossref","unstructured":"O. Goldreich, D. Ron, and M. Sudan. Chinese remaindering with errors. In Proc. of 31st STOC. ACM, 1999. Also available at [11]. The Electronic Colloquium on Computational Complexity.","DOI":"10.1145\/301250.301309"},{"key":"4_CR16","unstructured":"M. Gruber and C. G. Lekkerkerker. Geometry of Numbers. North-Holland, 1987."},{"issue":"6","key":"4_CR17","doi-asserted-by":"publisher","first-page":"1757","DOI":"10.1109\/18.782097","volume":"45","author":"V. Guruswami","year":"1999","unstructured":"V. Guruswami and M. Sudan. Improved decoding of Reed-Solomon and algebraicgeometric codes. IEEE Trans. on Information Theory, 45(6):1757\u20131767, 1999. An extended abstract appeared in the Proc. of IEEE FOCS\u2019 98.","journal-title":"IEEE Trans. on Information Theory"},{"key":"4_CR18","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/s001459900042","volume":"11","author":"A. Joux","year":"1998","unstructured":"A. Joux and J. Stern. Lattice reduction: A toolbox for the cryptanalyst. J. of Cryptology, 11:161\u2013185, 1998.","journal-title":"J. of Cryptology"},{"key":"4_CR19","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/3-540-48405-1_2","volume-title":"Proc. of Crypto\u2019 99","author":"A. Kipnis","year":"1999","unstructured":"A. Kipnis and A. Shamir. Cryptanalysis of the HFE public key cryptosystem by relinearization. In Proc. of Crypto\u2019 99, volume 1666 of LNCS, pages 19\u201330. Springer-Verlag, 1999."},{"key":"4_CR20","doi-asserted-by":"crossref","unstructured":"J. C. Lagarias and A. M. Odlyzko. Solving low-density subset sum problems. Journal of the Association for Computing Machinery, January 1985.","DOI":"10.1145\/2455.2461"},{"key":"4_CR21","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"A. K. Lenstra","year":"1982","unstructured":"A. K. Lenstra, H. W. Lenstra, and L. Lov\u00e1sz. Factoring polynomials with rational coefficients. Math. Ann., 261:515\u2013534, 1982.","journal-title":"Math. Ann."},{"key":"4_CR22","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/3-540-49264-X_7","volume-title":"Proc. of Eurocrypt\u2019 95","author":"R. Lercier","year":"1995","unstructured":"R. Lercier and F. Morain. Counting the number of points on elliptic curves over finite fields: strategies and performances. In Proc. of Eurocrypt\u2019 95, volume 921 of LNCS, pages 79\u201394. Springer-Verlag, 1995."},{"key":"4_CR23","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/BF01571276","volume":"110","author":"J. E. Mazo","year":"1990","unstructured":"J. E. Mazo and A. M. Odlyzko. Lattice points in high-dimensional spheres. Monatsh. Math., 110:47\u201361, 1990.","journal-title":"Monatsh. Math."},{"key":"4_CR24","unstructured":"D. Micciancio. The shortest vector problem is NP-hard to approximate within some constant. In Proc. 39th IEEE FOCS, 1998. Available at [11] as TR98-016."},{"key":"4_CR25","doi-asserted-by":"crossref","unstructured":"F. Monrose, M. Reiter, and S. Wetzel. Password hardening based on keystroke dynamics. In Proc. of 6th Conf. on Computer and Communications Security. ACM, 1999.","DOI":"10.1145\/319709.319720"},{"key":"4_CR26","doi-asserted-by":"crossref","unstructured":"M. Naor and B. Pinkas. Oblivious transfer and polynomial evaluation. In Proc. of 31st STOC, pages 245\u2013254. ACM, 1999.","DOI":"10.1145\/301250.301312"},{"key":"4_CR27","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1007\/BFb0052236","volume-title":"Proc. of Crypto\u2019 97","author":"P. Nguyen","year":"1997","unstructured":"P. Nguyen and J. Stern. Merkle-Hellman revisited: a cryptanalysis of the Qu-Vanstone cryptosystem based on group factorizations. In Proc. of Crypto\u2019 97, volume 1294 of LNCS, pages 198\u2013212. Springer-Verlag, 1997."},{"key":"4_CR28","unstructured":"R. Peralta and E. Okamoto. Faster factoring of integers of a special form. IEICE Trans. Fund. of Electronics, Communications, and Computer Sciences, 79(4), 1996."},{"key":"4_CR29","unstructured":"B. Pinkas, 1999. Private communication."},{"key":"4_CR30","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/0304-3975(87)90064-8","volume":"53","author":"C.-P. Schnorr","year":"1987","unstructured":"C.-P. Schnorr. A hierarchy of polynomial lattice basis reduction algorithms. Theoretical Computer Science, 53:201\u2013224, 1987.","journal-title":"Theoretical Computer Science"},{"key":"4_CR31","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/BF01581144","volume":"66","author":"C. P. Schnorr","year":"1994","unstructured":"C. P. Schnorr and M. Euchner. Lattice basis reduction: improved practical algorithms and solving subset sum problems. Math. Programming, 66:181\u2013199, 1994.","journal-title":"Math. Programming"},{"key":"4_CR32","series-title":"Lect Notes Comput Sci","first-page":"1","volume-title":"Proc. of Eurocrypt\u201995","author":"C.P. Schnorr","year":"1995","unstructured":"C.P. Schnorr and H.H. H\u00f6rner. Attacking the Chor-Rivest cryptosystem by improved lattice reduction. In Proc. of Eurocrypt\u201995, volume 921 of LNCS, pages 1\u201312. Springer-Verlag, 1995."},{"key":"4_CR33","doi-asserted-by":"crossref","first-page":"219","DOI":"10.5802\/jtnb.142","volume":"7","author":"R. Schoof","year":"1995","unstructured":"R. Schoof. Counting points on elliptic curves over finite fields. J. Th\u00e9or. Nombres Bordeaux, 7:219\u2013254, 1995.","journal-title":"J. Th\u00e9or. Nombres Bordeaux"},{"key":"4_CR34","unstructured":"V. Shoup. Number Theory Library (NTL) version 3.7a. Can be obtained at http:\/\/www.shoup.net\/ntl\/ ."},{"key":"4_CR35","doi-asserted-by":"crossref","unstructured":"C. L. Siegel. Lectures on the Geometry of Numbers. Springer-Verlag, 1989.","DOI":"10.1007\/978-3-662-08287-4"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2014 EUROCRYPT 2000"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45539-6_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,30]],"date-time":"2019-04-30T23:36:53Z","timestamp":1556667413000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45539-6_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540675174","9783540455394"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/3-540-45539-6_4","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2000]]}}}