{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T15:40:08Z","timestamp":1775230808604,"version":"3.50.1"},"reference-count":20,"publisher":"Wiley","issue":"A","license":[{"start":{"date-parts":[[2016,8,26]],"date-time":"2016-08-26T00:00:00Z","timestamp":1472169600000},"content-version":"unspecified","delay-in-days":238,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["LMS J. Comput. Math."],"published-print":{"date-parts":[[2016]]},"abstract":"<jats:p>The security of several homomorphic encryption schemes depends on the hardness of variants of the approximate common divisor (ACD) problem. We survey and compare a number of lattice-based algorithms for the ACD problem, with particular attention to some very recently proposed variants of the ACD problem. One of our main goals is to compare the multivariate polynomial approach with other methods. We find that the multivariate polynomial approach is not better than the orthogonal lattice algorithm for practical cryptanalysis.<\/jats:p><jats:p>We also briefly discuss a sample-amplification technique for ACD samples and a pre-processing algorithm similar to the Blum\u2013Kalai\u2013Wasserman algorithm for learning parity with noise. The details of this work are given in the full version of the paper.<\/jats:p>","DOI":"10.1112\/s1461157016000218","type":"journal-article","created":{"date-parts":[[2016,8,26]],"date-time":"2016-08-26T15:31:03Z","timestamp":1472225463000},"page":"58-72","source":"Crossref","is-referenced-by-count":43,"title":["Algorithms for the approximate common divisor problem"],"prefix":"10.1112","volume":"19","author":[{"given":"Steven D.","family":"Galbraith","sequence":"first","affiliation":[]},{"given":"Shishay W.","family":"Gebregiyorgis","sequence":"additional","affiliation":[]},{"given":"Sean","family":"Murphy","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2016,8,26]]},"reference":[{"key":"S1461157016000218_r18","doi-asserted-by":"publisher","DOI":"10.1007\/11792086_18"},{"key":"S1461157016000218_r1","unstructured":"1. M. Ajtai , \u2018Generating random lattices according to the invariant distribution\u2019, Preprint, 2006."},{"key":"S1461157016000218_r14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44371-2_13"},{"key":"S1461157016000218_r11","doi-asserted-by":"crossref","unstructured":"11. S. D. Galbraith , S. W. Gebregiyorgis and S. Murphy , \u2018Algorithms for the approximate common divisor problem\u2019, eprint 2016\/215 (2015).","DOI":"10.1112\/S1461157016000218"},{"key":"S1461157016000218_r13","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44670-2_6"},{"key":"S1461157016000218_r2","doi-asserted-by":"publisher","DOI":"10.1145\/792538.792543"},{"key":"S1461157016000218_r16","unstructured":"16. T. Lepoint , \u2018Design and implementation of lattice-based cryptography\u2019, PhD Thesis, Universit\u00e9 du Luxembourg and \u00c9cole Normale Sup\u00e9rieure (2014)."},{"key":"S1461157016000218_r4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38348-9_20"},{"key":"S1461157016000218_r9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13190-5_2"},{"key":"S1461157016000218_r12","unstructured":"12. S. W. Gebregiyorgis , \u2018Algorithms for the elliptic curve discrete logarithm and the approximate common divisor problem\u2019, PhD Thesis, University of Auckland, 2016."},{"key":"S1461157016000218_r7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22792-9_28"},{"key":"S1461157016000218_r20","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1111\/j.2517-6161.1965.tb00602.x","article-title":"Spacings","volume":"27","author":"Pyke","year":"1965","journal-title":"J. R. Stat. Soc. Ser. B"},{"key":"S1461157016000218_r8","first-page":"446","volume-title":"EUROCRYPT\u201912","author":"Coron","year":"2012"},{"key":"S1461157016000218_r15","doi-asserted-by":"publisher","DOI":"10.1007\/BF01457454"},{"key":"S1461157016000218_r10","unstructured":"10. J. Ding and C. Tao , \u2018A new algorithm for solving the general approximate common divisors problem and cryptanalysis of the FHE based on the GACD problem\u2019. Cryptology ePrint Archive, Report 2014\/042, 2014."},{"key":"S1461157016000218_r19","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44670-2_12"},{"key":"S1461157016000218_r3","first-page":"502","volume-title":"EUROCRYPT\u201912","author":"Chen","year":"2012"},{"key":"S1461157016000218_r17","first-page":"378","volume-title":"APPROX-RANDOM 2005","author":"Lyubashevsky","year":"2005"},{"key":"S1461157016000218_r6","first-page":"271","volume-title":"Proceedings of ANTS X","volume":"1","author":"Cohn","year":"2013"},{"key":"S1461157016000218_r5","first-page":"513","volume-title":"EUROCRYPT\u201915","author":"Cheon","year":"2015"}],"container-title":["LMS Journal of Computation and Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1461157016000218","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,19]],"date-time":"2024-06-19T02:37:56Z","timestamp":1718764676000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1461157016000218\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"references-count":20,"journal-issue":{"issue":"A","published-print":{"date-parts":[[2016]]}},"alternative-id":["S1461157016000218"],"URL":"https:\/\/doi.org\/10.1112\/s1461157016000218","relation":{},"ISSN":["1461-1570"],"issn-type":[{"value":"1461-1570","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]}}}