{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T10:20:16Z","timestamp":1772878816618,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642390586","type":"print"},{"value":"9783642390593","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-39059-3_9","type":"book-chapter","created":{"date-parts":[[2013,6,14]],"date-time":"2013-06-14T01:33:17Z","timestamp":1371173597000},"page":"118-135","source":"Crossref","is-referenced-by-count":21,"title":["Better Lattice Constructions for Solving Multivariate Linear Equations Modulo Unknown Divisors"],"prefix":"10.1007","author":[{"given":"Atsushi","family":"Takayasu","sequence":"first","affiliation":[]},{"given":"Noboru","family":"Kunihiro","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"9_CR1","unstructured":"Bellare, M., Rogaway, P.: Probabilistic signature scheme. US Patent 6266771 (2001)"},{"key":"9_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-48910-X_1","volume-title":"Advances in Cryptology - EUROCRYPT \u201999","author":"D. Boneh","year":"1999","unstructured":"Boneh, D., Durfee, G.: Cryptanalysis of RSA with private key d less than N\n                  0.292. IEEE Trans. Inf. Theory 46(4), 1339\u20131349 (2000); Firstly appeared In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol.\u00a01592, pp. 1\u201311. Springer, Heidelberg (1999)"},{"key":"9_CR3","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.\u00a07237, pp. 502\u2013519. Springer, Heidelberg (2012)"},{"key":"9_CR4","unstructured":"Cohn, H., Heninger, N.: Approximate common divisors via lattices. Report 2011\/437 in the Cryptology ePrint Archive (2011), \n                    \n                      http:\/\/eprint.iacr.org\/2011\/437\n                    \n                    \n                   (to appear at Proc. of ANTS-X)"},{"key":"9_CR5","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.\u00a01070, pp. 155\u2013165. Springer, Heidelberg (1996)"},{"issue":"4","key":"9_CR6","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. Journal of Cryptology\u00a010(4), 233\u2013260 (1997)","journal-title":"Journal of Cryptology"},{"key":"9_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"444","DOI":"10.1007\/978-3-642-04138-9_31","volume-title":"Cryptographic Hardware and Embedded Systems - CHES 2009","author":"J.-S. Coron","year":"2009","unstructured":"Coron, J.-S., Joux, A., Kizhvatov, I., Naccache, D., Paillier, P.: Fault Attacks on RSA Signatures with partially unknown messages. In: Clavier, C., Gaj, K. (eds.) CHES 2009. LNCS, vol.\u00a05747, pp. 444\u2013456. Springer, Heidelberg (2009)"},{"key":"9_CR8","unstructured":"Coron, J.-S., Lepoint, T., Tibouchi, M.: Batch Fully Homomorphic Encryption over the Integers. Report 2013\/036 in the Cryptology ePrint Archive (2013), \n                    \n                      http:\/\/eprint.iacr.org\/2013\/036"},{"key":"9_CR9","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.\u00a06841, pp. 487\u2013504. Springer, Heidelberg (2011)"},{"key":"9_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1007\/978-3-642-11925-5_15","volume-title":"Topics in Cryptology - CT-RSA 2010","author":"J.-S. Coron","year":"2010","unstructured":"Coron, J.-S., Naccache, D., Tibouchi, M.: Fault Attacks Against emv Signatures. In: Pieprzyk, J. (ed.) CT-RSA 2010. LNCS, vol.\u00a05985, pp. 208\u2013220. Springer, Heidelberg (2010)"},{"key":"9_CR11","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.\u00a07237, pp. 446\u2013464. Springer, Heidelberg (2012)"},{"key":"9_CR12","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. Dijk van","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":"9_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1007\/978-3-642-33027-8_26","volume-title":"Cryptographic Hardware and Embedded Systems \u2013 CHES 2012","author":"P.-A. Fouque","year":"2012","unstructured":"Fouque, P.-A., Guillermin, N., Leresteux, D., Tibouchi, M., Zapalowicz, J.-C.: Attacking RSA-CRT Signatures with Faults on Montgomery Multiplication. In: Prouff, E., Schaumont, P. (eds.) CHES 2012. LNCS, vol.\u00a07428, pp. 447\u2013462. Springer, Heidelberg (2012)"},{"key":"9_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1007\/978-3-642-21969-6_6","volume-title":"Progress in Cryptology \u2013 AFRICACRYPT 2011","author":"M. Herrmann","year":"2011","unstructured":"Herrmann, M.: Improved Cryptanalysis of the Multi-Prime \u03a6-Hiding Assumption. In: Nitaj, A., Pointcheval, D. (eds.) AFRICACRYPT 2011. LNCS, vol.\u00a06737, pp. 92\u201399. Springer, Heidelberg (2011)"},{"key":"9_CR15","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.\u00a05350, pp. 406\u2013424. Springer, Heidelberg (2008)"},{"key":"9_CR16","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.\u00a01355, pp. 131\u2013142. Springer, Heidelberg (1997)"},{"key":"9_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":"9_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/978-3-642-14623-7_16","volume-title":"Advances in Cryptology \u2013 CRYPTO 2010","author":"E. Kiltz","year":"2010","unstructured":"Kiltz, E., O\u2019Neill, A., Smith, A.: Instantiability of RSA-OAEP under Chosen-Plaintext Attack. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol.\u00a06223, pp. 295\u2013313. Springer, Heidelberg (2010)"},{"key":"9_CR19","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"A.K. Lenstra","year":"1982","unstructured":"Lenstra, A.K., Lenstra, H.W., Lov\u00e1sz, L.: Factoring polynomials with rational coefficients. Mathematische Annalen\u00a0261, 515\u2013534 (1982)","journal-title":"Mathematische Annalen"},{"key":"9_CR20","unstructured":"May, A.: New RSA Vulnerabilities Using Lattice Reduction Methods. PhD thesis, University of Paderborn (2003)"},{"key":"9_CR21","unstructured":"May, A.: Using LLL-reduction for solving RSA and factorization problems: A survey (2007), \n                    \n                      http:\/\/www.cits.rub.de\/permonen\/may.html"},{"key":"9_CR22","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.\u00a05443, pp. 1\u201314. Springer, Heidelberg (2009)"},{"key":"9_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1007\/978-3-642-34416-9_10","volume-title":"Security, Privacy, and Applied Cryptography Engineering","author":"S. Sarkar","year":"2012","unstructured":"Sarkar, S.: Reduction in Lossiness of RSA Trapdoor Permutation. In: Bogdanov, A., Sanadhya, S. (eds.) SPACE 2012. LNCS, vol.\u00a07644, pp. 144\u2013152. Springer, Heidelberg (2012)"},{"issue":"4","key":"9_CR24","doi-asserted-by":"publisher","first-page":"4002","DOI":"10.1109\/TIT.2011.2137270","volume":"57","author":"S. Sarkar","year":"2011","unstructured":"Sarkar, S., Maitra, S.: Approximate Integer Common Divisor Problem relates to Implicit Factorization. IEEE Trans. Inf. Theory\u00a057(4), 4002\u20134013 (2011)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-31448-3_1","volume-title":"Information Security and Privacy","author":"K. Tosu","year":"2012","unstructured":"Tosu, K., Kunihiro, N.: Optimal Bounds for Multi-Prime \u03a6-Hiding Assumption. In: Susilo, W., Mu, Y., Seberry, J. (eds.) ACISP 2012. LNCS, vol.\u00a07372, pp. 1\u201314. Springer, Heidelberg (2012)"}],"container-title":["Lecture Notes in Computer Science","Information Security and Privacy"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-39059-3_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,10,11]],"date-time":"2018-10-11T18:54:06Z","timestamp":1539284046000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-39059-3_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642390586","9783642390593"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-39059-3_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}