{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T21:44:09Z","timestamp":1762033449485},"publisher-location":"Singapore","reference-count":65,"publisher":"Springer Singapore","isbn-type":[{"type":"print","value":"9789811050640"},{"type":"electronic","value":"9789811050657"}],"license":[{"start":{"date-parts":[[2017,7,26]],"date-time":"2017-07-26T00:00:00Z","timestamp":1501027200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-981-10-5065-7_16","type":"book-chapter","created":{"date-parts":[[2017,7,25]],"date-time":"2017-07-25T13:58:39Z","timestamp":1500991119000},"page":"297-312","source":"Crossref","is-referenced-by-count":3,"title":["Recent Progress on Coppersmith\u2019s Lattice-Based Method: A Survey"],"prefix":"10.1007","author":[{"given":"Yao","family":"Lu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Liqiang","family":"Peng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Noboru","family":"Kunihiro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,7,26]]},"reference":[{"key":"16_CR1","unstructured":"A. Bauer, D. Vergnaud, J. Zapalowicz, Inferring sequences produced by nonlinear pseudorandom number generators using Coppersmith\u2019s methods, in PKC 2012 (2012), pp. 609\u2013626"},{"key":"16_CR2","unstructured":"J. Bl\u00f6mer, A. May, New partial key exposure attacks on RSA, in CRYPTO 2003 (2003), pp. 27\u201343"},{"issue":"4","key":"16_CR3","doi-asserted-by":"crossref","first-page":"1339","DOI":"10.1109\/18.850673","volume":"46","author":"D Boneh","year":"2000","unstructured":"D. Boneh, G. Durfee, Cryptanalysis of RSA with private key $$d$$ less than $$N^{0.292}$$ . IEEE Trans. Inf. Theory 46(4), 1339\u20131349 (2000)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"16_CR4","unstructured":"D. Boneh, G. Durfee, Y. Frankel, An attack on RSA given a small fraction of the private key bits, in ASIACRYPT 1998 (1998), pp. 25\u201334"},{"key":"16_CR5","doi-asserted-by":"crossref","unstructured":"H. Cohn, N. Heninger, Approximate common divisors via lattices, in ANTS-X (2012)","DOI":"10.2140\/obs.2013.1.271"},{"key":"16_CR6","unstructured":"D. Coppersmith, Finding a small root of a bivariate integer equation; factoring with high bits known, in EUROCRYPT 1996 (1996), pp. 178\u2013189"},{"key":"16_CR7","unstructured":"D. Coppersmith, Finding a small root of a univariate modular equation, in EUROCRYPT 1996 (1996), pp. 155\u2013165"},{"issue":"1","key":"16_CR8","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/s00145-006-0433-6","volume":"20","author":"J Coron","year":"2007","unstructured":"J. Coron, A. May, Deterministic polynomial-time equivalence of computing the RSA secret key and factoring. J. Cryptol. 20(1), 39\u201350 (2007)","journal-title":"J. Cryptol."},{"key":"16_CR9","unstructured":"J. Coron, A. Joux, I. Kizhvatov, D. Naccache, P. Paillier, Fault attacks on RSA signatures with partially unknown messages, in CHES 2009 (2009), pp. 444\u2013456"},{"key":"16_CR10","unstructured":"J. Coron, D. Naccache, M. Tibouchi, Fault attacks against EMV signatures, in CT-RSA 2010 (2010), pp. 208\u2013220"},{"key":"16_CR11","unstructured":"M.J. Coster, B.A. LaMacchia, A.M. Odlyzko, An improved low-density subset sum algorithm, in EUROCRYPT 1991 (1991), pp. 54\u201367"},{"key":"16_CR12","unstructured":"G. Durfee, P.Q. Nguyen, Cryptanalysis of the RSA schemes with short secret exponent from Asiacrypt\u201999, in ASIACRYPT 2000 (2000), pp. 14\u201329"},{"key":"16_CR13","unstructured":"M. Ernst, E. Jochemsz, A. May, B. de Weger, Partial key exposure attacks on RSA up to full size exponents, in EUROCRYPT 2005 (2005), pp. 371\u2013384"},{"issue":"1","key":"16_CR14","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/s13389-013-0050-x","volume":"3","author":"PA Fouque","year":"2013","unstructured":"P.A. Fouque, N. Guillermin, D. Leresteux, M. Tibouchi, J.C. Zapalowicz, Attacking RSA-CRT signatures with faults on montgomery multiplication. J. Cryptogr. Eng. 3(1), 59\u201372 (2013)","journal-title":"J. Cryptogr. Eng."},{"key":"16_CR15","unstructured":"M. Herrmann, Improved cryptanalysis of the multi-prime $$\\phi $$ -hiding assumption, in AFRICACRYPT 2011 (2011), pp. 92\u201399"},{"key":"16_CR16","unstructured":"M. Herrmann, Lattice-based cryptanalysis using unravelled linearization. Ph.D. thesis, der Ruhr-Universitat Bochum (2011), http:\/\/www-brs.ub.ruhr-uni-bochum.de\/netahtml\/HSS\/Diss\/HerrmannMathias\/diss.pdf"},{"key":"16_CR17","unstructured":"M. Herrmann, A. May, Solving linear equations modulo divisors: on factoring given any bits, in ASIACRYPT 2008 (2008), pp. 406\u2013424"},{"key":"16_CR18","unstructured":"M. Herrmann, A. May, Attacking power generators using unravelled linearization: when do we output too much? in ASIACRYPT 2009 (2009), pp. 487\u2013504"},{"key":"16_CR19","unstructured":"M. Herrmann, A. May, Maximizing small root bounds by linearization and applications to small secret exponent RSA, in PKC 2010 (2010), pp. 53\u201369"},{"key":"16_CR20","unstructured":"N. Howgrave-Graham, Finding small roots of univariate modular equations revisited, in Cryptography and Coding 1997 (1997), pp. 131\u2013142"},{"key":"16_CR21","unstructured":"N. Howgrave-Graham, Approximate integer common divisors, in CaLC 2001 (2001), pp. 51\u201366"},{"key":"16_CR22","unstructured":"Z. Huang, L. Hu, J. Xu, Attacking RSA with a composed decryption exponent using unravelled linearization, in Inscrypt 2014 (2014), pp. 207\u2013219"},{"key":"16_CR23","unstructured":"E. Jochemsz, A. May, A strategy for finding roots of multivariate polynomials with new applications in attacking RSA variants, in ASIACRYPT 2006 (2006), pp. 267\u2013282"},{"key":"16_CR24","unstructured":"E. Jochemsz, A. May, A polynomial time attack on RSA with private CRT-exponents smaller than $$N^{0.073}$$ , in CRYPTO 2007 (2006), pp. 395\u2013411"},{"key":"16_CR25","unstructured":"T. Kleinjung, K. Aoki, J. Franke, A.K. Lenstra, E. Thom\u00e9, J.W. Bos, P. Gaudry, A. Kruppa, P.L. Montgomery, D.A. Osvik, H.J.J. te Riele, A. Timofeev, P. Zimmermann, Factorization of a 768-bit RSA modulus, in CRYPTO 2010 (2010), pp. 333\u2013350"},{"key":"16_CR26","unstructured":"N. Kunihiro, On optimal bounds of small inverse problems and approximate GCD problmes with higher degree, in ISC 2012 (2012), pp. 55\u201369"},{"key":"16_CR27","unstructured":"N. Kunihiro, K. Kurosawa, Deterministic polynomial time equivalence between factoring and key-recovery attack on Takagi\u2019s RSA, in PKC 2007 (2007), pp. 412\u2013425"},{"key":"16_CR28","doi-asserted-by":"crossref","unstructured":"N. Kunihiro, N. Shinohara, T. Izu, A unified framework for small secret exponent attack on RSA. IEICE Trans. 97-A(6), 1285\u20131295 (2014)","DOI":"10.1587\/transfun.E97.A.1285"},{"key":"16_CR29","doi-asserted-by":"crossref","unstructured":"J.C. Lagarias, A.M. Odlyzko, Solving low-density subset sum problems. J. ACM 32(1), 229\u2013246 (1985)","DOI":"10.1145\/2455.2461"},{"issue":"4","key":"16_CR30","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"AK Lenstra","year":"1982","unstructured":"A.K. Lenstra, H.W. Lenstra, L. Lov\u00e1sz, Factoring polynomials with rational coefficients. Math. Ann. 261(4), 515\u2013534 (1982)","journal-title":"Math. Ann."},{"key":"16_CR31","unstructured":"A.K. Lenstra, E. Tromer, A. Shamir, W. Kortsmit, B. Dodson, J.P. Hughes, P.C. Leyland, Factoring estimates for a 1024-bit RSA modulus, in ASIACRYPT 2003 (2003), pp. 55\u201374"},{"key":"16_CR32","unstructured":"Y. Lu, R. Zhang, D. Lin, Factoring RSA modulus with known bits from both $$p$$ and $$q$$ : a lattice method, in NSS 2013 (2013), pp. 393\u2013404"},{"key":"16_CR33","unstructured":"Y. Lu, R. Zhang, D. Lin, Factoring multi-power RSA modulus $$N=p^rq$$ with partial known bits, in ACISP 2013 (2013), pp. 57\u201371"},{"key":"16_CR34","unstructured":"Y. Lu, R. Zhang, D. Lin, New partial key exposure attacks on CRT-RSA with large public exponents, in ACNS 2014 (2014), pp. 151\u2013162"},{"key":"16_CR35","unstructured":"Y. Lu, R. Zhang, L. Peng, D. Lin, Solving linear equations modulo unknown divisors: revisited, in ASIACRYPT 2015, Part I (2015), pp. 189\u2013213"},{"key":"16_CR36","unstructured":"A. May, New RSA vulnerabilities using lattice reduction methods. Ph.D. thesis, University of Paderborn (2003), http:\/\/ubdata.uni-paderborn.de\/ediss\/17\/2003\/may\/disserta.pdf"},{"key":"16_CR37","unstructured":"A. May, Secret exponent attacks on RSA-type schemes with moduli $$N=p^rq$$ , in PKC 2004 (2004), pp. 218\u2013230"},{"key":"16_CR38","unstructured":"A. May, Computing the RSA secret key is deterministic polynomial time equivalent to factoring, in CRYPTO 2004 (2004), pp. 213\u2013219"},{"key":"16_CR39","doi-asserted-by":"crossref","unstructured":"A. May, M. Ritzenhofen, Implicit factoring: on polynomial time factoring given only an implicit hint, in Proceedings of the PKC 2009 (2009), pp. 1\u201314","DOI":"10.1007\/978-3-642-00468-1_1"},{"key":"16_CR40","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1201\/9781439821916","volume-title":"Handbook of Applied Cryptography","author":"AJ Menezes","year":"1996","unstructured":"A.J. Menezes, P.C. van Oorschot, S.A. Vanstone, Handbook of Applied Cryptography (CRC Press, Boca Raton, 1996), pp. 118\u2013122"},{"key":"16_CR41","doi-asserted-by":"crossref","unstructured":"P.Q. Nguyen, B. Vall\u00e9e (eds.), The LLL Algorithm - Survey and Applications. Information Security and Cryptography (Springer, Heidelberg, 2010)","DOI":"10.1007\/978-3-642-02295-1"},{"key":"16_CR42","unstructured":"L. Peng, L. Hu, J. Xu, Z. Huang, Y. Xie, Further improvement of factoring RSA moduli with implicit hint, in AFRICACRYPT 2014 (2014), pp. 165\u2013177"},{"key":"16_CR43","doi-asserted-by":"crossref","unstructured":"L. Peng, L. Hu, Y. Lu, H. Wei, An improved analysis on three variants of the RSA cryptosystem. To appear in Inscrypt (2016)","DOI":"10.1007\/978-3-319-54705-3_9"},{"key":"16_CR44","doi-asserted-by":"publisher","unstructured":"L. Peng, L. Hu, Y. Lu, J. Xu, Z. Huang, Cryptanalysis of dual RSA. Des. Codes Cryptogr. (2016). doi: 10.1007\/s10623-016-0196-5","DOI":"10.1007\/s10623-016-0196-5"},{"issue":"2","key":"16_CR45","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1145\/359340.359342","volume":"21","author":"RL Rivest","year":"1978","unstructured":"R.L. Rivest, A. Shamir, L.M. Adleman, A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120\u2013126 (1978)","journal-title":"Commun. ACM"},{"issue":"2","key":"16_CR46","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1007\/s10623-014-9928-6","volume":"73","author":"S Sarkar","year":"2014","unstructured":"S. Sarkar, Small secret exponent attack on RSA variant with modulus $$N=p^rq$$ . Des. Codes Cryptogr. 73(2), 383\u2013392 (2014)","journal-title":"Des. Codes Cryptogr."},{"key":"16_CR47","doi-asserted-by":"crossref","unstructured":"S. Sarkar, Revisiting prime power RSA. Discret. Appl. Math. 203, 127\u2013133 (2016)","DOI":"10.1016\/j.dam.2015.10.003"},{"key":"16_CR48","unstructured":"S. Sarkar, S. Maitra, Partial key exposure attack on CRT-RSA, in ACNS 2009 (2009), pp. 473\u2013484"},{"issue":"6","key":"16_CR49","doi-asserted-by":"crossref","first-page":"4002","DOI":"10.1109\/TIT.2011.2137270","volume":"57","author":"S Sarkar","year":"2011","unstructured":"S. Sarkar, S. Maitra, Approximate integer common divisor problem relates to implicit factorization. IEEE Trans. Inf. Theory 57(6), 4002\u20134013 (2011)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"16_CR50","unstructured":"P.W. Shor, Algorithms for quantum computation: discrete log and factoring, in FOCS 1994 (1994), pp. 124\u2013134"},{"issue":"8","key":"16_CR51","doi-asserted-by":"crossref","first-page":"2922","DOI":"10.1109\/TIT.2007.901248","volume":"53","author":"H Sun","year":"2007","unstructured":"H. Sun, M. Wu, W. Ting, M.J. Hinek, Dual RSA and its security analysis. IEEE Trans. Inf. Theory 53(8), 2922\u20132933 (2007)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"16_CR52","unstructured":"A. Takayasu, N. Kunihiro, Better lattice constructions for solving multivariate linear equations modulo unknown divisors, in ACISP 2013 (2013), pp. 118\u2013135"},{"key":"16_CR53","unstructured":"A. Takayasu, N. Kunihiro, Cryptanalysis of RSA with multiple small secret exponents, in ACISP 2014 (2014), pp. 176\u2013191"},{"key":"16_CR54","unstructured":"A. Takayasu, N. Kunihiro, Partial key exposure attacks on RSA: achieving the Boneh-Durfee bound, in SAC 2014 (2014), pp. 345\u2013362"},{"key":"16_CR55","unstructured":"A. Takayasu, N. Kunihiro, Partial key exposure attacks on CRT-RSA: better cryptanalysis to full size encryption exponents, in ACNS 2015 (2015), pp. 518\u2013537"},{"key":"16_CR56","unstructured":"A. Takayasu, N. Kunihiro, Partial key exposure attacks on RSA with multiple exponent pairs, in ACISP 2016 (2016), pp. 243\u2013257"},{"key":"16_CR57","unstructured":"A. Takayasu, N. Kunihiro, How to generalize RSA cryptanalysis, in PKC 2016, Part II (2016), pp. 67\u201397"},{"key":"16_CR58","unstructured":"A. Takayasu, N. Kunihiro, Partial key exposure attacks on CRT-RSA: general improvement for the exposed least significant bits, in ISC 2016 (2016), pp. 35\u201347"},{"key":"16_CR59","unstructured":"A. Takayasu, N. Kunihiro, Small secret exponent attacks on RSA with unbalanced prime factors, in ISITA 2016 (2016), pp. 236\u2013240"},{"key":"16_CR60","doi-asserted-by":"crossref","unstructured":"A. Takayasu, N. Kunihiro, A tool kit for partial key exposure attacks on RSA. To appear in CT-RSA 2017 (2017)","DOI":"10.1007\/978-3-319-52153-4_4"},{"key":"16_CR61","doi-asserted-by":"crossref","unstructured":"A. Takayasu, N. Kunihiro, General bounds for small inverse problems and its applications to multi-prime RSA. IEICE Trans. 100-A(1), 50\u201361 (2017)","DOI":"10.1587\/transfun.E100.A.50"},{"key":"16_CR62","doi-asserted-by":"crossref","unstructured":"A. Takayasu, Y. Lu, L. Peng, Small CRT-exponent RSA revisited. To appear in EUROCRYPT 2017 (2017)","DOI":"10.1007\/978-3-319-56614-6_5"},{"key":"16_CR63","unstructured":"K. Tosu, N. Kunihiro, Optimal bounds for multi-prime $$\\phi $$ -hiding assumption, in ACISP 2012 (2012), pp. 1\u201314"},{"key":"16_CR64","unstructured":"M. van Dijk, C. Gentry, S. Halevi, V. Vaikuntanathan, Fully homomorphic encryption over the integers, in EUROCRYPT 2010 (2010), pp. 24\u201343"},{"issue":"3","key":"16_CR65","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1109\/18.54902","volume":"36","author":"MJ Wiener","year":"1990","unstructured":"M.J. Wiener, Cryptanalysis of short RSA secret exponents. IEEE Trans. Inf. Theory 36(3), 553\u2013558 (1990)","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Mathematics for Industry","Mathematical Modelling for Next-Generation Cryptography"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-10-5065-7_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,1]],"date-time":"2019-10-01T15:33:25Z","timestamp":1569944005000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-981-10-5065-7_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,7,26]]},"ISBN":["9789811050640","9789811050657"],"references-count":65,"URL":"https:\/\/doi.org\/10.1007\/978-981-10-5065-7_16","relation":{},"ISSN":["2198-350X","2198-3518"],"issn-type":[{"type":"print","value":"2198-350X"},{"type":"electronic","value":"2198-3518"}],"subject":[],"published":{"date-parts":[[2017,7,26]]}}}