{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T03:08:21Z","timestamp":1743131301288,"version":"3.40.3"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031157769"},{"type":"electronic","value":"9783031157776"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"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":[[2022]]},"DOI":"10.1007\/978-3-031-15777-6_3","type":"book-chapter","created":{"date-parts":[[2022,8,23]],"date-time":"2022-08-23T15:24:33Z","timestamp":1661268273000},"page":"37-54","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["New Results of\u00a0Breaking the\u00a0CLS Scheme from\u00a0ACM-CCS 2014"],"prefix":"10.1007","author":[{"given":"Jing","family":"Gao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jun","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tianyu","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lei","family":"Hu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,8,24]]},"reference":[{"key":"3_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/978-3-540-72540-4_21","volume-title":"Advances in Cryptology - EUROCRYPT 2007","author":"A Bauer","year":"2007","unstructured":"Bauer, A., Joux, A.: Toward a rigorous variation of Coppersmith\u2019s algorithm on three variables. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 361\u2013378. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-72540-4_21"},{"key":"3_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1007\/978-3-642-29011-4_30","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2012","author":"Y Chen","year":"2012","unstructured":"Chen, Y., Nguyen, P.Q.: Faster algorithms for approximate common divisors: breaking fully-homomorphic-encryption challenges over the integers. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 502\u2013519. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-29011-4_30"},{"issue":"1","key":"3_CR3","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1515\/jmc-2019-0031","volume":"14","author":"JH Cheon","year":"2020","unstructured":"Cheon, J.H., Cho, W., Hhan, M., Kim, J., Lee, C.: Algorithms for CRT-variant of approximate greatest common divisor problem. J. Math. Cryptol. 14(1), 397\u2013413 (2020)","journal-title":"J. Math. Cryptol."},{"key":"3_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/978-3-642-38348-9_20","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2013","author":"JH Cheon","year":"2013","unstructured":"Cheon, J.H., Coron, J.-S., Kim, J., Lee, M.S., Lepoint, T., Tibouchi, M., Yun, A.: Batch fully homomorphic encryption over the integers. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 315\u2013335. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-38348-9_20"},{"key":"3_CR5","doi-asserted-by":"crossref","unstructured":"Cheon, J.H., Lee, H.T., Seo, J.H.: A new additive homomorphic encryption based on the co-ACD problem. In: Ahn, G., Yung, M., Li, N. (eds.) ACM SIGSAC Conference on Computer and Communications Security, pp. 287\u2013298. ACM (2014)","DOI":"10.1145\/2660267.2660335"},{"key":"3_CR6","unstructured":"Cohn, H., Heninger, N.: Approximate common divisors via lattices. CoRR abs\/1108.2714 (2011)"},{"key":"3_CR7","doi-asserted-by":"publisher","first-page":"2988","DOI":"10.1109\/TIFS.2020.2981239","volume":"15","author":"EL Cominetti Jr","year":"2020","unstructured":"Cominetti, E.L., Jr., Simplicio, M.A.: Fast additive partially homomorphic encryption from the approximate common divisor problem. IEEE Trans. Inf. Forensics Secur. 15, 2988\u20132998 (2020)","journal-title":"IEEE Trans. Inf. Forensics Secur."},{"key":"3_CR8","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 \u2014 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. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 178\u2013189. Springer, Heidelberg (1996). https:\/\/doi.org\/10.1007\/3-540-68339-9_16"},{"key":"3_CR9","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 \u2014 EUROCRYPT \u201996","author":"D Coppersmith","year":"1996","unstructured":"Coppersmith, D.: Finding a small root of a univariate modular equation. In: Maurer, U. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 155\u2013165. Springer, Heidelberg (1996). https:\/\/doi.org\/10.1007\/3-540-68339-9_14"},{"issue":"4","key":"3_CR10","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. Cryptol. 10(4), 233\u2013260 (1997)","journal-title":"J. Cryptol."},{"key":"3_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1007\/978-3-319-29485-8_26","volume-title":"Topics in Cryptology - CT-RSA 2016","author":"J-S Coron","year":"2016","unstructured":"Coron, J.-S., Faug\u00e8re, J.-C., Renault, G., Zeitoun, R.: Factoring $$N=p^rq^s$$ for large r and s. In: Sako, K. (ed.) CT-RSA 2016. LNCS, vol. 9610, pp. 448\u2013464. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-29485-8_26"},{"key":"3_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/978-3-642-22792-9_28","volume-title":"Advances in Cryptology \u2013 CRYPTO 2011","author":"J-S Coron","year":"2011","unstructured":"Coron, J.-S., Mandal, A., Naccache, D., Tibouchi, M.: Fully homomorphic encryption over the integers with shorter public keys. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 487\u2013504. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-22792-9_28"},{"key":"3_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"446","DOI":"10.1007\/978-3-642-29011-4_27","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2012","author":"J-S Coron","year":"2012","unstructured":"Coron, J.-S., Naccache, D., Tibouchi, M.: Public key compression and modulus switching for fully homomorphic encryption over the integers. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 446\u2013464. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-29011-4_27"},{"key":"3_CR14","unstructured":"Coron, J., Notarnicola, L., Wiese, G.: Simultaneous diagonalization of incomplete matrices and applications. CoRR abs\/2005.13629 (2020)"},{"key":"3_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/978-3-319-76953-0_4","volume-title":"Topics in Cryptology \u2013 CT-RSA 2018","author":"J-S Coron","year":"2018","unstructured":"Coron, J.-S., Zeitoun, R.: Improved factorization of $$N=p^rq^s$$. In: Smart, N.P. (ed.) CT-RSA 2018. LNCS, vol. 10808, pp. 65\u201379. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-76953-0_4"},{"key":"3_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/978-3-642-13190-5_2","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2010","author":"M van Dijk","year":"2010","unstructured":"van Dijk, M., Gentry, C., Halevi, S., Vaikuntanathan, V.: Fully homomorphic encryption over the integers. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 24\u201343. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-13190-5_2"},{"key":"3_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1007\/978-3-662-47989-6_27","volume-title":"Advances in Cryptology \u2013 CRYPTO 2015","author":"P-A Fouque","year":"2015","unstructured":"Fouque, P.-A., Lee, M.S., Lepoint, T., Tibouchi, M.: Cryptanalysis of the co-ACD assumption. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 561\u2013580. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-47989-6_27"},{"key":"3_CR18","doi-asserted-by":"crossref","unstructured":"Galbraith, S.D., Gebregiyorgis, S.W., Murphy, S.: Algorithms for the approximate common divisor problem. IACR Cryptology ePrint Archive, p. 215 (2016)","DOI":"10.1112\/S1461157016000218"},{"key":"3_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/978-3-642-13013-7_4","volume-title":"Public Key Cryptography \u2013 PKC 2010","author":"M Herrmann","year":"2010","unstructured":"Herrmann, M., May, A.: Maximizing small root bounds by linearization and applications to small secret exponent RSA. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 53\u201369. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-13013-7_4"},{"key":"3_CR20","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). https:\/\/doi.org\/10.1007\/BFb0024458"},{"key":"3_CR21","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). https:\/\/doi.org\/10.1007\/3-540-44670-2_6"},{"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). https:\/\/doi.org\/10.1007\/11935230_18"},{"key":"3_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/978-3-540-74143-5_22","volume-title":"Advances in Cryptology - CRYPTO 2007","author":"E Jochemsz","year":"2007","unstructured":"Jochemsz, E., May, A.: A polynomial time attack on RSA with private CRT-exponents smaller than $$N^{0.073}$$. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 395\u2013411. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-74143-5_22"},{"key":"3_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"404","DOI":"10.1007\/978-3-642-34961-4_25","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2012","author":"SA Kakvi","year":"2012","unstructured":"Kakvi, S.A., Kiltz, E., May, A.: Certifying RSA. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 404\u2013414. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-34961-4_25"},{"key":"3_CR25","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"A Lenstra","year":"1982","unstructured":"Lenstra, A.: Factoring polynomial with rational coefficients. Mathematiche Annalen 261, 515\u2013534 (1982)","journal-title":"Mathematiche Annalen"},{"key":"3_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/978-3-662-48797-6_9","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2015","author":"Y Lu","year":"2015","unstructured":"Lu, Y., Zhang, R., Peng, L., Lin, D.: Solving linear equations modulo unknown divisors: revisited. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9452, pp. 189\u2013213. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48797-6_9"},{"key":"3_CR27","unstructured":"May, A.: 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":"3_CR28","series-title":"Information Security and Cryptography","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/978-3-642-02295-1_10","volume-title":"The LLL Algorithm - Survey and Applications","author":"A May","year":"2010","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. ISC, pp. 315\u2013348. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-02295-1_10"},{"key":"3_CR29","doi-asserted-by":"crossref","unstructured":"May, A., Nowakowski, J., Sarkar, S.: Partial key exposure attack on short secret exponent CRT-RSA. IACR Cryptology ePrint Archive, p. 972 (2021)","DOI":"10.1007\/978-3-030-92062-3_4"},{"key":"3_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1007\/BFb0052236","volume-title":"Advances in Cryptology \u2014 CRYPTO \u201997","author":"P Nguyen","year":"1997","unstructured":"Nguyen, P., Stern, J.: Merkle-Hellman revisited: a cryptanalysis of the Qu-Vanstone cryptosystem based on group factorizations. In: Kaliski, B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 198\u2013212. Springer, Heidelberg (1997). https:\/\/doi.org\/10.1007\/BFb0052236"},{"key":"3_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1007\/3-540-48892-8_17","volume-title":"Selected Areas in Cryptography","author":"P Nguyen","year":"1999","unstructured":"Nguyen, P., Stern, J.: Cryptanalysis of a fast public key cryptosystem presented at SAC \u201997. In: Tavares, S., Meijer, H. (eds.) SAC 1998. LNCS, vol. 1556, pp. 213\u2013218. Springer, Heidelberg (1999). https:\/\/doi.org\/10.1007\/3-540-48892-8_17"},{"key":"3_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/3-540-48405-1_3","volume-title":"Advances in Cryptology \u2014 CRYPTO\u2019 99","author":"P Nguyen","year":"1999","unstructured":"Nguyen, P., Stern, J.: The hardness of the hidden subset sum problem and its cryptographic implications. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 31\u201346. Springer, Heidelberg (1999). https:\/\/doi.org\/10.1007\/3-540-48405-1_3"},{"key":"3_CR33","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/j.tcs.2020.07.004","volume":"841","author":"K Suzuki","year":"2020","unstructured":"Suzuki, K., Takayasu, A., Kunihiro, N.: Extended partial key exposure attacks on RSA: improvement up to full size decryption exponents. Theor. Comput. Sci. 841, 62\u201383 (2020)","journal-title":"Theor. Comput. Sci."},{"key":"3_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1007\/978-3-030-26948-7_11","volume-title":"Advances in Cryptology \u2013 CRYPTO 2019","author":"J Xu","year":"2019","unstructured":"Xu, J., Sarkar, S., Hu, L., Wang, H., Pan, Y.: New results on modular inversion hidden number problem and inversive congruential generator. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11692, pp. 297\u2013321. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-26948-7_11"}],"container-title":["Lecture Notes in Computer Science","Information and Communications Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-15777-6_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T17:06:32Z","timestamp":1709831192000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-15777-6_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031157769","9783031157776"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-15777-6_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"24 August 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}