{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T10:05:08Z","timestamp":1771668308204,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662493861","type":"print"},{"value":"9783662493878","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-49387-8_3","type":"book-chapter","created":{"date-parts":[[2016,2,17]],"date-time":"2016-02-17T14:25:41Z","timestamp":1455719141000},"page":"36-66","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Easing Coppersmith Methods Using Analytic Combinatorics: Applications to Public-Key Cryptography with Weak Pseudorandomness"],"prefix":"10.1007","author":[{"given":"Fabrice","family":"Benhamouda","sequence":"first","affiliation":[]},{"given":"C\u00e9line","family":"Chevalier","sequence":"additional","affiliation":[]},{"given":"Adrian","family":"Thillard","sequence":"additional","affiliation":[]},{"given":"Damien","family":"Vergnaud","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,2,18]]},"reference":[{"key":"3_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-13708-2_1","volume-title":"Applied Cryptography and Network Security","author":"A Bauer","year":"2010","unstructured":"Bauer, A., Coron, J.-S., Naccache, D., Tibouchi, M., Vergnaud, D.: On the broadcast and validity-checking security of pkcs#1 v1.5 encryption. In: Zhou, J., Yung, M. (eds.) ACNS 2010. LNCS, vol. 6123, pp. 1\u201318. Springer, Heidelberg (2010)"},{"key":"3_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"609","DOI":"10.1007\/978-3-642-30057-8_36","volume-title":"Public Key Cryptography \u2013 PKC 2012","author":"A Bauer","year":"2012","unstructured":"Bauer, A., Vergnaud, D., Zapalowicz, J.-C.: Inferring sequences produced by nonlinear pseudorandom number generators using Coppersmith\u2019s methods. In: Fischlin, M., Buchmann, J., Manulis, M. (eds.) PKC 2012. LNCS, vol. 7293, pp. 609\u2013626. Springer, Heidelberg (2012)"},{"key":"3_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/978-3-642-10366-7_14","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2009","author":"M Bellare","year":"2009","unstructured":"Bellare, M., Brakerski, Z., Naor, M., Ristenpart, T., Segev, G., Shacham, H., Yilek, S.: Hedged public-key encryption: how to protect against bad randomness. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 232\u2013249. Springer, Heidelberg (2009)"},{"key":"3_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/BFb0052242","volume-title":"Advances in Cryptology - CRYPTO \u201997","author":"M Bellare","year":"1997","unstructured":"Bellare, M., Goldwasser, S., Micciancio, D.: \u201cPseudo-random\u201d number generation within cryptographic algorithms: the DSS case. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 277\u2013291. Springer, Heidelberg (1997)"},{"issue":"251","key":"3_CR5","doi-asserted-by":"publisher","first-page":"1471","DOI":"10.1090\/S0025-5718-04-01698-9","volume":"74","author":"SR Blackburn","year":"2005","unstructured":"Blackburn, S.R., G\u00f3mez-P\u00e9rez, D., Gutierrez, J., Shparlinski, I.: Predicting nonlinear pseudorandom number generators. Math. Comput. 74(251), 1471\u20131494 (2005)","journal-title":"Math. Comput."},{"issue":"2","key":"3_CR6","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/j.jalgor.2004.07.002","volume":"61","author":"SR Blackburn","year":"2006","unstructured":"Blackburn, S.R., G\u00f3mez-P\u00e9rez, D., Gutierrez, J., Shparlinski, I.: Reconstructing noisy polynomial evaluation in residue rings. J. Algorithms 61(2), 47\u201359 (2006)","journal-title":"J. Algorithms"},{"key":"3_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BFb0055716","volume-title":"Advances in Cryptology - CRYPTO \u201998","author":"D Bleichenbacher","year":"1998","unstructured":"Bleichenbacher, D.: Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 1\u201312. Springer, Heidelberg (1998)"},{"key":"3_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/11426639_15","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2005","author":"J Bl\u00f6mer","year":"2005","unstructured":"Bl\u00f6mer, J., May, A.: A tool kit for finding small roots of bivariate polynomials over the integers. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 251\u2013267. Springer, Heidelberg (2005)"},{"issue":"3","key":"3_CR9","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/BF02252875","volume":"1","author":"J Boyar","year":"1989","unstructured":"Boyar, J.: Inferring sequences produced by a linear congruential generator missing low-order bits. J. Cryptology 1(3), 177\u2013184 (1989)","journal-title":"J. Cryptology"},{"issue":"1","key":"3_CR10","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1145\/58562.59305","volume":"36","author":"J Boyar","year":"1989","unstructured":"Boyar, J.: Inferring sequences produced by pseudo-random number generators. J. ACM 36(1), 129\u2013141 (1989)","journal-title":"J. ACM"},{"key":"3_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1007\/3-540-68339-9_16","volume-title":"Advances in Cryptology - EUROCRYPT \u201996","author":"D Coppersmith","year":"1996","unstructured":"Coppersmith, D.: Finding a small root of a bivariate integer equation; factoring with high bits known. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 178\u2013189. Springer, Heidelberg (1996)"},{"key":"3_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/3-540-68339-9_14","volume-title":"Advances in Cryptology - EUROCRYPT \u201996","author":"D Coppersmith","year":"1996","unstructured":"Coppersmith, D.: Finding a small root of a univariate modular equation. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 155\u2013165. Springer, Heidelberg (1996)"},{"issue":"4","key":"3_CR13","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/s001459900030","volume":"10","author":"D Coppersmith","year":"1997","unstructured":"Coppersmith, D.: Small solutions to polynomial equations, and low exponent RSA vulnerabilities. J. Cryptology 10(4), 233\u2013260 (1997)","journal-title":"J. Cryptology"},{"key":"3_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/3-540-45539-6_25","volume-title":"Advances in Cryptology - EUROCRYPT 2000","author":"J-S Coron","year":"2000","unstructured":"Coron, J.-S., Joye, M., Naccache, D., Paillier, P.: New attacks on PKCS#1 v1.5 encryption. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 369\u2013381. Springer, Heidelberg (2000)"},{"key":"3_CR15","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511801655","volume-title":"Analytic Combinatorics","author":"P Flajolet","year":"2009","unstructured":"Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009)"},{"key":"3_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1007\/978-3-642-45239-0_10","volume-title":"Cryptography and Coding","author":"P-A Fouque","year":"2013","unstructured":"Fouque, P.-A., Tibouchi, M., Zapalowicz, J.-C.: Recovering private keys generated with weak PRNGs. In: Stam, M. (ed.) IMACC 2013. LNCS, vol. 8308, pp. 158\u2013172. Springer, Heidelberg (2013)"},{"issue":"2","key":"3_CR17","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1016\/0022-0000(84)90070-9","volume":"28","author":"S Goldwasser","year":"1984","unstructured":"Goldwasser, S., Micali, S.: Probabilistic encryption. J. Comput. Syst. Sci. 28(2), 270\u2013299 (1984)","journal-title":"J. Comput. Syst. Sci."},{"key":"3_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/978-3-642-10366-7_29","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2009","author":"M Herrmann","year":"2009","unstructured":"Herrmann, M., May, A.: Attacking power generators using unravelled linearization: when do we output too much? In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 487\u2013504. Springer, Heidelberg (2009)"},{"key":"3_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"590","DOI":"10.1007\/978-3-642-32009-5_35","volume-title":"Advances in Cryptology \u2013 CRYPTO 2012","author":"D Hofheinz","year":"2012","unstructured":"Hofheinz, D., Jager, T.: Tightly secure signatures and public-key encryption. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 590\u2013607. Springer, Heidelberg (2012)"},{"key":"3_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/BFb0024458","volume-title":"Cryptography and Coding","author":"N Howgrave-Graham","year":"1997","unstructured":"Howgrave-Graham, N.: Finding small roots of univariate modular equations revisited. In: Darnell, M. (ed.) Cryptography and Coding 1997. LNCS, vol. 1355, pp. 131\u2013142. Springer, Heidelberg (1997)"},{"key":"3_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"752","DOI":"10.1007\/978-3-642-33167-1_43","volume-title":"Computer Security \u2013 ESORICS 2012","author":"T Jager","year":"2012","unstructured":"Jager, T., Schinzel, S., Somorovsky, J.: Bleichenbacher\u2019s attack strikes again: breaking PKCS#1 v1.5 in XML encryption. In: Foresti, S., Yung, M., Martinelli, F. (eds.) ESORICS 2012. LNCS, vol. 7459, pp. 752\u2013769. Springer, Heidelberg (2012)"},{"key":"3_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/11935230_18","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2006","author":"E Jochemsz","year":"2006","unstructured":"Jochemsz, E., May, A.: A strategy for finding roots of multivariate polynomials with new applications in attacking RSA variants. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 267\u2013282. Springer, Heidelberg (2006)"},{"issue":"3","key":"3_CR23","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/s001459900042","volume":"11","author":"A Joux","year":"1998","unstructured":"Joux, A., Stern, J.: Lattice reduction: a toolbox for the cryptanalyst. J. Cryptology 11(3), 161\u2013185 (1998)","journal-title":"J. Cryptology"},{"key":"3_CR24","doi-asserted-by":"crossref","unstructured":"Kaliski, B.: PKCS #1: RSA Encryption Version 1.5. RFC 2313, Internet Engineering Task Force, March 1998. \n                      http:\/\/www.rfc-editor.org\/rfc\/rfc2313.txt","DOI":"10.17487\/rfc2313"},{"key":"3_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1007\/3-540-45664-3_3","volume-title":"Public Key Cryptography","author":"T Koshiba","year":"2002","unstructured":"Koshiba, T.: On sufficient randomness for secure public-key cryptosystems. In: Naccache, D., Paillier, P. (eds.) PKC 2002. LNCS, vol. 2274, pp. 34\u201347. Springer, Heidelberg (2002)"},{"key":"3_CR26","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41422-0","volume-title":"People, Problems, and Proofs - Essays from G\u00f6del\u2019s Lost Letter: 2010","author":"RJ Lipton","year":"2013","unstructured":"Lipton, R.J., Regan, K.W.: People, Problems, and Proofs - Essays from G\u00f6del\u2019s Lost Letter: 2010. Springer, Berlin (2013)"},{"key":"3_CR27","first-page":"315","volume-title":"The LLL Algorithm","author":"Alexander May","year":"2009","unstructured":"May, A.: Using lll-reduction for solving RSA and factorization problems. In: Nguyen, P.Q., Vall\u00e9e, B. (eds.) The LLL Algorithm - Survey and Applications. Information Security and Cryptography, pp. 315\u2013348, Springer, Heidelberg (2010). \n                      http:\/\/dx.org\/10.1007\/978-3-642-02295-1"},{"key":"3_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/978-3-540-78440-1_3","volume-title":"Public Key Cryptography \u2013 PKC 2008","author":"A May","year":"2008","unstructured":"May, A., Ritzenhofen, M.: Solving systems of modular equations in one variable: how many RSA-encrypted messages does eve need to know? In: Cramer, R. (ed.) PKC 2008. LNCS, vol. 4939, pp. 37\u201346. Springer, Heidelberg (2008)"},{"key":"3_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-00468-1_1","volume-title":"Public Key Cryptography \u2013 PKC 2009","author":"A May","year":"2009","unstructured":"May, A., Ritzenhofen, M.: Implicit factoring: on polynomial time factoring given only an implicit hint. In: Jarecki, S., Tsudik, G. (eds.) PKC 2009. LNCS, vol. 5443, pp. 1\u201314. Springer, Heidelberg (2009)"},{"key":"3_CR30","unstructured":"Ritzenhofen, M.: On efficiently calculating small solutions of systems of polynomial equations: lattice-based methods and applications to cryptography. Ph.D. thesis, Ruhr University Bochum (2010). \n                      http:\/\/www-brs.ub.ruhr-uni-bochum.de\/netahtml\/HSS\/Diss\/RitzenhofenMaike\/"},{"key":"3_CR31","doi-asserted-by":"crossref","unstructured":"Stern, J.: Secret linear congruential generators are not cryptographically secure. In: 28th FOCS, pp. 421\u2013426. IEEE Computer Society Press, October 1987","DOI":"10.1109\/SFCS.1987.51"}],"container-title":["Lecture Notes in Computer Science","Public-Key Cryptography \u2013 PKC 2016"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-49387-8_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,2,18]],"date-time":"2020-02-18T11:20:02Z","timestamp":1582024802000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-49387-8_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662493861","9783662493878"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-49387-8_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"18 February 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}