{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T11:10:51Z","timestamp":1778152251236,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642290107","type":"print"},{"value":"9783642290114","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-29011-4_30","type":"book-chapter","created":{"date-parts":[[2012,4,5]],"date-time":"2012-04-05T07:05:53Z","timestamp":1333609553000},"page":"502-519","source":"Crossref","is-referenced-by-count":66,"title":["Faster Algorithms for Approximate Common Divisors: Breaking Fully-Homomorphic-Encryption Challenges over the Integers"],"prefix":"10.1007","author":[{"given":"Yuanmi","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Phong Q.","family":"Nguyen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"30_CR1","doi-asserted-by":"publisher","first-page":"1339","DOI":"10.1109\/18.850673","volume":"46","author":"D. Boneh","year":"2000","unstructured":"Boneh, D., Durfee, G.: Cryptanalysis of RSA with private key d less than $N^{\\mbox{0.292}}$ . IEEE Transactions on Information Theory\u00a046(4), 1339 (2000)","journal-title":"IEEE Transactions on Information Theory"},{"issue":"6","key":"30_CR2","doi-asserted-by":"publisher","first-page":"1777","DOI":"10.1137\/S0097539704443793","volume":"36","author":"A. Bostan","year":"2007","unstructured":"Bostan, A., Gaudry, P., Schost, E.: Linear recurrences with polynomial coefficients and application to integer factorization and Cartier-Manin operator. SIAM Journal on Computing\u00a036(6), 1777\u20131806 (2007)","journal-title":"SIAM Journal on Computing"},{"key":"30_CR3","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) LWE. Cryptology ePrint Archive, Report 2011\/344 (2011), http:\/\/eprint.iacr.org\/","DOI":"10.1109\/FOCS.2011.12"},{"key":"30_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-25385-0_1","volume-title":"ASIACRYPT 2011","author":"Y. Chen","year":"2011","unstructured":"Chen, Y., Nguyen, P.Q.: BKZ 2.0: Better Lattice Security Estimates. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol.\u00a07073, pp. 1\u201320. Springer, Heidelberg (2011)"},{"key":"30_CR5","doi-asserted-by":"crossref","unstructured":"Chen, Y., Nguyen, P.Q.: Faster Algorithms for Approximate Common Divisors: Breaking Fully-Homomorphic-Encryption Challenges over the Integers. Cryptology ePrint Archive, Report 2011\/436 (2011), http:\/\/eprint.iacr.org\/","DOI":"10.1007\/978-3-642-29011-4_30"},{"key":"30_CR6","unstructured":"Cohn, H., Heninger, N.: Approximate common divisors via lattices. Cryptology ePrint Archive, Report 2011\/437 (2011)"},{"issue":"4","key":"30_CR7","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\u00a010(4), 233\u2013260 (1997)","journal-title":"J. Cryptology"},{"key":"30_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/978-3-642-19379-8_9","volume-title":"Public Key Cryptography \u2013 PKC 2011","author":"J.-S. Coron","year":"2011","unstructured":"Coron, J.-S., Joux, A., Mandal, A., Naccache, D., Tibouchi, M.: Cryptanalysis of the RSA Subgroup Assumption from TCC 2005. In: Catalano, D., Fazio, N., Gennaro, R., Nicolosi, A. (eds.) PKC 2011. LNCS, vol.\u00a06571, pp. 147\u2013155. Springer, Heidelberg (2011)"},{"key":"30_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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.\u00a06841, pp. 487\u2013504. Springer, Heidelberg (2011)"},{"key":"30_CR10","doi-asserted-by":"crossref","unstructured":"Coron, J.-S., Naccache, D., Tibouchi, M.: Public Key Compression and Modulus Switching for Fully Homomorphic Encryption over the Integers. Cryptology ePrint Archive, Report 2011\/440 (2011), http:\/\/eprint.iacr.org\/","DOI":"10.1007\/978-3-642-22792-9_28"},{"key":"30_CR11","doi-asserted-by":"crossref","unstructured":"Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Proc. STOC 2009, pp. 169\u2013178. ACM (2009)","DOI":"10.1145\/1536414.1536440"},{"key":"30_CR12","unstructured":"Gentry, C., Halevi, S.: Public challenges for fully-homomorphic encryption. The implementation is described in [12] (2010), https:\/\/researcher.ibm.com\/researcher\/view_project.php?id=1548"},{"key":"30_CR13","doi-asserted-by":"crossref","unstructured":"Gentry, C., Halevi, S.: Fully homomorphic encryption without squashing using depth-3 arithmetic circuits. Cryptology ePrint Archive, Report 2011\/279 (2011), http:\/\/eprint.iacr.org\/","DOI":"10.1109\/FOCS.2011.94"},{"key":"30_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/978-3-642-20465-4_9","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2011","author":"C. Gentry","year":"2011","unstructured":"Gentry, C., Halevi, S.: Implementing Gentry\u2019s Fully-Homomorphic Encryption Scheme. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol.\u00a06632, pp. 129\u2013148. Springer, Heidelberg (2011)"},{"key":"30_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1007\/978-3-540-30576-7_4","volume-title":"Theory of Cryptography","author":"J. Groth","year":"2005","unstructured":"Groth, J.: Cryptography in Subgroups of ${\\mathbb{Z}_n^*}$ . In: Kilian, J. (ed.) TCC 2005. LNCS, vol.\u00a03378, pp. 50\u201365. Springer, Heidelberg (2005)"},{"key":"30_CR16","doi-asserted-by":"crossref","unstructured":"Harvey, D., Roche, D.S.: An in-place truncated fourier transform and applications to polynomial multiplication. In: Proc. ISSAC 2010, pp. 325\u2013329. ACM (2010)","DOI":"10.1145\/1837934.1837996"},{"key":"30_CR17","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.\u00a02146, pp. 51\u201366. Springer, Heidelberg (2001)"},{"key":"30_CR18","unstructured":"Mateer, T.: Fast Fourier Transform Algorithms with Applications. PhD thesis, Clemson University (2008)"},{"key":"30_CR19","doi-asserted-by":"crossref","unstructured":"May, A.: Using LLL-reduction for solving RSA and factorization problems: A survey. In: [21] (2010)","DOI":"10.1007\/978-3-642-02295-1_10"},{"key":"30_CR20","unstructured":"Montgomery, P.L.: An FFT Extension of the Elliptic Curve Method of Factorization. PhD thesis, University of California Los Angeles (1992)"},{"key":"30_CR21","doi-asserted-by":"crossref","unstructured":"Nguyen, P.Q.: Public-key cryptanalysis. In: Luengo, I. (ed.) Recent Trends in Cryptography. Contemporary Mathematics, vol.\u00a0477. AMS\u2013RSME (2009)","DOI":"10.1090\/conm\/477\/09304"},{"key":"30_CR22","volume-title":"The LLL Algorithm: Survey and Applications. Information Security and Cryptography","year":"2010","unstructured":"Nguyen, P.Q., Vall\u00e9e, B. (eds.): The LLL Algorithm: Survey and Applications. Information Security and Cryptography. Springer, Heidelberg (2010)"},{"key":"30_CR23","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1017\/S0305004100049252","volume":"76","author":"J.M. Pollard","year":"1974","unstructured":"Pollard, J.M.: Theorems on factorization and primality testing. Proc. Cambridge Philos. Soc.\u00a076, 521\u2013528 (1974)","journal-title":"Proc. Cambridge Philos. Soc."},{"key":"30_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/10721064_32","volume-title":"Smart Card. Research and Applications","author":"G. Qiao","year":"2000","unstructured":"Qiao, G., Lam, K.-Y.: RSA Signature Algorithm for Microcontroller Implementation. In: Schneier, B., Quisquater, J.-J. (eds.) CARDIS 1998. LNCS, vol.\u00a01820, pp. 353\u2013356. Springer, Heidelberg (2000)"},{"key":"30_CR25","doi-asserted-by":"crossref","unstructured":"Roche, D.S.: Space- and time-efficient polynomial multiplication. In: Proc. ISSAC 2009, pp. 295\u2013302. ACM (2009)","DOI":"10.1145\/1576702.1576743"},{"key":"30_CR26","unstructured":"Shoup, V.: Number Theory C++ Library (NTL) version 5.4.1, http:\/\/www.shoup.net\/ntl\/"},{"issue":"237","key":"30_CR27","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1090\/S0025-5718-01-01310-2","volume":"71","author":"D.R. Stinson","year":"2002","unstructured":"Stinson, D.R.: Some baby-step giant-step algorithms for the low hamming weight discrete logarithm problem. Math. Comput.\u00a071(237), 379\u2013391 (2002)","journal-title":"Math. Comput."},{"issue":"1","key":"30_CR28","first-page":"1","volume":"78","author":"V. Strassen","year":"1976","unstructured":"Strassen, V.: Einige Resultate \u00fcber Berechnungskomplexit\u00e4t. Jber. Deutsch. Math.-Verein.\u00a078(1), 1\u20138 (1976\/1977)","journal-title":"Jber. Deutsch. Math.-Verein."},{"key":"30_CR29","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.\u00a06110, pp. 24\u201343. Springer, Heidelberg (2010)"},{"key":"30_CR30","unstructured":"von Zur Gathen, J., Gerhard, J.: Modern computer algebra, 2nd edn. Cambridge University Press (2003)"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 EUROCRYPT 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-29011-4_30.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T13:52:58Z","timestamp":1742910778000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-29011-4_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642290107","9783642290114"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-29011-4_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}