{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,27]],"date-time":"2025-04-27T05:20:23Z","timestamp":1745731223298,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662538869"},{"type":"electronic","value":"9783662538876"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-53887-6_28","type":"book-chapter","created":{"date-parts":[[2016,11,8]],"date-time":"2016-11-08T12:11:21Z","timestamp":1478607081000},"page":"759-788","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Cryptographic Applications of Capacity Theory: On the Optimality of Coppersmith\u2019s Method for Univariate Polynomials"],"prefix":"10.1007","author":[{"given":"Ted","family":"Chinburg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Brett","family":"Hemenway","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nadia","family":"Heninger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zachary","family":"Scherr","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,11,9]]},"reference":[{"key":"28_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1007\/978-3-642-31448-3_28","volume-title":"Information Security and Privacy","author":"Y Aono","year":"2012","unstructured":"Aono, Y., Agrawal, M., Satoh, T., Watanabe, O.: On the optimality of lattices for the Coppersmith technique. In: Susilo, W., Mu, Y., Seberry, J. (eds.) ACISP 2012. LNCS, vol. 7372, pp. 376\u2013389. Springer, Heidelberg (2012). doi:10.1007\/978-3-642-31448-3_28"},{"issue":"2","key":"28_CR2","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1137\/0217013","volume":"17","author":"W Alexi","year":"1988","unstructured":"Alexi, W., Chor, B., Goldreich, O., Schnorr, C.-P.: RSA and Rabin functions: certain parts are as hard as the whole. SIAM J. Comput. 17(2), 194\u2013209 (1988)","journal-title":"SIAM J. Comput."},{"issue":"8","key":"28_CR3","doi-asserted-by":"publisher","first-page":"1853","DOI":"10.1002\/j.1538-7305.1967.tb03174.x","volume":"46","author":"ER Berlekamp","year":"1967","unstructured":"Berlekamp, E.R.: Factoring polynomials over finite fields. Bell Syst. Tech. J. 46(8), 1853\u20131859 (1967)","journal-title":"Bell Syst. Tech. J."},{"key":"28_CR4","doi-asserted-by":"crossref","unstructured":"Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: CCS 1993, pp. 62\u201373. ACM Press (1993)","DOI":"10.1145\/168588.168596"},{"key":"28_CR5","first-page":"160","volume":"316","author":"DG Cantor","year":"1980","unstructured":"Cantor, D.G.: On an extension of the definition of transfinite diameter and some applications. J. Reine Angew. Math. 316, 160\u2013207 (1980)","journal-title":"J. Reine Angew. Math."},{"issue":"1","key":"28_CR6","first-page":"75","volume":"80","author":"T Chinburg","year":"1991","unstructured":"Chinburg, T.: Capacity theory on varieties. Compositio Math. 80(1), 75\u201384 (1991)","journal-title":"Compositio Math."},{"key":"28_CR7","doi-asserted-by":"crossref","unstructured":"Chinburg, T., Moret-Bailly, L., Pappas, G., Taylor, M.J.: Finite morphisms to projective space and capacity theory. J. fur die Reine und. Angew. Math. (2015)","DOI":"10.1515\/crelle-2014-0089"},{"issue":"4","key":"28_CR8","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":"28_CR9","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1007\/3-540-44670-2_3","volume":"2146","author":"D Coppersmith","year":"2001","unstructured":"Coppersmith, D.: Finding small solutions to small degree polynomials. Crypt. Lattices 2146, 20\u201331 (2001)","journal-title":"Crypt. Lattices"},{"issue":"154","key":"28_CR10","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1090\/S0025-5718-1981-0606517-5","volume":"36","author":"DG Cantor","year":"1981","unstructured":"Cantor, D.G., Zassenhaus, H.: A new algorithm for factoring polynomials over finite fields. Math. Comput. 36(154), 587\u2013592 (1981)","journal-title":"Math. Comput."},{"issue":"1","key":"28_CR11","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1007\/BF01504345","volume":"17","author":"M Fekete","year":"1923","unstructured":"Fekete, M.: \u00dcber die verteilung der wurzeln bei gewissen algebraischen gleichungen mit ganzzahligen koeffizienten. Math. Z. 17(1), 228\u2013249 (1923)","journal-title":"Math. Z."},{"issue":"1","key":"28_CR12","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1007\/BF01187931","volume":"63","author":"M Fekete","year":"1955","unstructured":"Fekete, M., Szeg\u00f6, G.: On algebraic equations with integral coefficients whose roots belong to a given point set. Math. Z. 63(1), 158\u2013172 (1955)","journal-title":"Math. Z."},{"issue":"2","key":"28_CR13","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/s001459910008","volume":"13","author":"R Fischlin","year":"2000","unstructured":"Fischlin, R., Schnorr, C.-P.: Stronger security proofs for RSA and Rabin bits. J. Cryptology 13(2), 221\u2013244 (2000)","journal-title":"J. Cryptology"},{"key":"28_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/BFb0024458","volume-title":"Crytography 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). doi:10.1007\/BFb0024458"},{"key":"28_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/3-540-44670-2_6","volume-title":"Cryptography and Lattices","author":"N Howgrave-Graham","year":"2001","unstructured":"Howgrave-Graham, N.: Approximate integer common divisors. In: Silverman, J.H. (ed.) CaLC 2001. LNCS, vol. 2146, pp. 51\u201366. Springer, Heidelberg (2001). doi:10.1007\/3-540-44670-2_6"},{"key":"28_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1007\/978-3-540-89255-7_25","volume-title":"Advances in Cryptology - ASIACRYPT 2008","author":"M Herrmann","year":"2008","unstructured":"Herrmann, M., May, A.: Solving linear equations modulo divisors: on factoring given any bits. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 406\u2013424. Springer, Heidelberg (2008). doi:10.1007\/978-3-540-89255-7_25"},{"issue":"2","key":"28_CR17","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1145\/972639.972642","volume":"51","author":"J H\u00e5stad","year":"2004","unstructured":"H\u00e5stad, J., N\u00e5slund, M.: The security of all RSA and discrete log bits. J. ACM (JACM) 51(2), 187\u2013230 (2004)","journal-title":"J. ACM (JACM)"},{"key":"28_CR18","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). doi:10.1007\/11935230_18"},{"key":"28_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1007\/BFb0054124","volume-title":"Advances in Cryptology \u2014 EUROCRYPT 1998","author":"CS Jutla","year":"1998","unstructured":"Jutla, C.S.: On finding small solutions of modular multivariate polynomial equations. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 158\u2013170. Springer, Heidelberg (1998). doi:10.1007\/BFb0054124"},{"issue":"4","key":"28_CR20","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"HW Lenstra","year":"1982","unstructured":"Lenstra, H.W., Lenstra, A.K., Lov\u00e1sz, L.: Factoring polynomials with rational coeficients. Math. Ann. 261(4), 515\u2013534 (1982)","journal-title":"Math. Ann."},{"key":"28_CR21","unstructured":"May, A.: Using LLL-reduction for solving RSA, factorization problems: a survey. In: Conference Proceedings of the Conference in Honor of the 25th Birthday of the LLL Algorithm, pp. 1\u201334 (2007)"},{"key":"28_CR22","first-page":"315","volume-title":"The LLL Algorithm Information Security and Cryptography, Chap. 10","author":"A May","year":"2010","unstructured":"May, A.: Using LLL-reduction for solving RSA and factorization problems the LLL algorithm. In: Nguyen, P.Q., Vall\u00e9e, B. (eds.) The LLL Algorithm Information Security and Cryptography, Chap. 10, pp. 315\u2013348. Springer, Heidelberg (2010)"},{"issue":"690","key":"28_CR23","first-page":"viii+130","volume":"145","author":"R Rumely","year":"2000","unstructured":"Rumely, R., Lau, C.F., Varley, R.: Existence of the sectional capacity. Mem. Am. Math. Soc. 145(690), viii+130 (2000)","journal-title":"Mem. Am. Math. Soc."},{"key":"28_CR24","first-page":"64","volume":"6","author":"JB Rosser","year":"1962","unstructured":"Rosser, J.B., Schoenfeld, L.: Approximate formulas for some functions of prime numbers. Ill. J. Math. 6, 64\u201394 (1962)","journal-title":"Ill. J. Math."},{"key":"28_CR25","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0084525","volume-title":"Capacity Theory on Algebraic Curves","author":"RS Rumely","year":"1989","unstructured":"Rumely, R.S.: Capacity Theory on Algebraic Curves. LNM, vol. 1378. Springer, Heidelberg (1989). doi:10.1007\/BFb0084525"},{"key":"28_CR26","series-title":"Mathematical Surveys and Monographs","doi-asserted-by":"crossref","DOI":"10.1090\/surv\/193","volume-title":"Capacity Theory with Local Rationality","author":"R Rumely","year":"2013","unstructured":"Rumely, R.: Capacity Theory with Local Rationality. Mathematical Surveys and Monographs, vol. 193. American Mathematical Society, Providence (2013). The strong Fekete-Szeg\u00f6 theorem on curves"},{"key":"28_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/3-540-44647-8_15","volume-title":"Advances in Cryptology \u2014 CRYPTO 2001","author":"V Shoup","year":"2001","unstructured":"Shoup, V.: OAEP reconsidered. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 239\u2013259. Springer, Heidelberg (2001). doi:10.1007\/3-540-44647-8_15"},{"key":"28_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/11935230_13","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2006","author":"R Steinfeld","year":"2006","unstructured":"Steinfeld, R., Pieprzyk, J., Wang, H.: On the provable security of an efficient RSA-based pseudorandom generator. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 194\u2013209. Springer, Heidelberg (2006). doi:10.1007\/11935230_13"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 ASIACRYPT 2016"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-53887-6_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T17:09:42Z","timestamp":1710263382000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-53887-6_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662538869","9783662538876"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-53887-6_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"9 November 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ASIACRYPT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on the Theory and Application of Cryptology and Information Security","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hanoi","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Vietnam","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2016","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 December 2016","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 December 2016","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"asiacrypt2016","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.asiacrypt2016.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}