{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T22:27:05Z","timestamp":1768343225367,"version":"3.49.0"},"reference-count":19,"publisher":"Walter de Gruyter GmbH","issue":"1","license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,10,20]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>The approximate greatest common divisor problem (ACD) and its variants have been used to construct many cryptographic primitives. In particular, the variants of the ACD problem based on Chinese remainder theorem (CRT) are being used in the constructions of a batch fully homomorphic encryption to encrypt multiple messages in one ciphertext. Despite the utility of the CRT-variant scheme, the algorithms that secures its security foundation have not been probed well enough.<\/jats:p>\n                  <jats:p>\n                    In this paper, we propose two algorithms and the results of experiments in which the proposed algorithms were used to solve the variant problem. Both algorithms take the same time complexity\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/j_jmc-2015-0031_eq_001.png\"\/>\n                        <m:math xmlns:m=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <m:mtable>\n                            <m:mtr>\n                              <m:mtd>\n                                <m:mstyle>\n                                  <m:msup>\n                                    <m:mn>2<\/m:mn>\n                                    <m:mrow>\n                                      <m:mrow>\n                                        <m:mover>\n                                          <m:mi>O<\/m:mi>\n                                          <m:mo>~<\/m:mo>\n                                        <\/m:mover>\n                                      <\/m:mrow>\n                                      <m:mo>(<\/m:mo>\n                                      <m:mfrac>\n                                        <m:mi>\u03b3<\/m:mi>\n                                        <m:mrow>\n                                          <m:mo>(<\/m:mo>\n                                          <m:mi>\u03b7<\/m:mi>\n                                          <m:mo>\u2212<\/m:mo>\n                                          <m:mi>\u03c1<\/m:mi>\n                                          <m:msup>\n                                            <m:mo>)<\/m:mo>\n                                            <m:mn>2<\/m:mn>\n                                          <\/m:msup>\n                                        <\/m:mrow>\n                                      <\/m:mfrac>\n                                      <m:mo>)<\/m:mo>\n                                    <\/m:mrow>\n                                  <\/m:msup>\n                                <\/m:mstyle>\n                              <\/m:mtd>\n                            <\/m:mtr>\n                          <\/m:mtable>\n                        <\/m:math>\n                        <jats:tex-math>$\\begin{array}{}\n\\displaystyle\n2^{\\tilde{O}(\\frac{\\gamma}{(\\eta-\\rho)^2})}\n\\end{array}$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    up to a polynomial factor to solve the variant problem for the bit size of samples\n                    <jats:italic>\u03b3<\/jats:italic>\n                    , secret primes\n                    <jats:italic>\u03b7<\/jats:italic>\n                    , and error bound\n                    <jats:italic>\u03c1<\/jats:italic>\n                    . Our algorithm gives the first parameter condition related to\n                    <jats:italic>\u03b7<\/jats:italic>\n                    and\n                    <jats:italic>\u03b3<\/jats:italic>\n                    size. From the results of the experiments, it has been proved that the proposed algorithms work well both in theoretical and experimental terms.\n                  <\/jats:p>","DOI":"10.1515\/jmc-2019-0031","type":"journal-article","created":{"date-parts":[[2020,11,3]],"date-time":"2020-11-03T09:52:13Z","timestamp":1604397133000},"page":"397-413","source":"Crossref","is-referenced-by-count":4,"title":["Algorithms for CRT-variant of Approximate Greatest Common Divisor Problem"],"prefix":"10.1515","volume":"14","author":[{"given":"Jung Hee","family":"Cheon","sequence":"first","affiliation":[{"name":"Seoul National University , 1 Gwanak-ro, 08826 , Seoul , South Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wonhee","family":"Cho","sequence":"additional","affiliation":[{"name":"Seoul National University , 1 Gwanak-ro, 08826 , Seoul , South Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Minki","family":"Hhan","sequence":"additional","affiliation":[{"name":"Seoul National University , 1 Gwanak-ro, 08826 , Seoul , South Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiseung","family":"Kim","sequence":"additional","affiliation":[{"name":"Seoul National University , 1 Gwanak-ro, 08826 , Seoul , South Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Changmin","family":"Lee","sequence":"additional","affiliation":[{"name":"ENS de Lyon, Laboratoire LIP (U. Lyon, CNRS, ENSL, INRIA, UCBL) , 46 All\u00e9e d\u2019Italie, 69007 , Lyon , France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"374","published-online":{"date-parts":[[2020,10,20]]},"reference":[{"key":"2025120600172418531_j_jmc-2015-0031_ref_001_w2aab3b7e1594b1b6b1ab2b1b1Aa","unstructured":"M. Ajtai. Generating random lattices according to the invariant distribution. draft, (2006)."},{"key":"2025120600172418531_j_jmc-2015-0031_ref_002_w2aab3b7e1594b1b6b1ab2b1b2Aa","doi-asserted-by":"crossref","unstructured":"L. Babai. On lov\u00e1sz\u2019lattice reduction and the nearest lattice point problem. Combinatorica, 6(1):1\u201313, 1986.","DOI":"10.1007\/BF02579403"},{"key":"2025120600172418531_j_jmc-2015-0031_ref_003_w2aab3b7e1594b1b6b1ab2b1b3Aa","doi-asserted-by":"crossref","unstructured":"Y. Chen and P. Q. Nguyen. Faster algorithms for approximate common divisors: Breaking fully-homomorphic-encryption challenges over the integers. Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 502\u2013519, 2012.","DOI":"10.1007\/978-3-642-29011-4_30"},{"key":"2025120600172418531_j_jmc-2015-0031_ref_004_w2aab3b7e1594b1b6b1ab2b1b4Aa","doi-asserted-by":"crossref","unstructured":"J. H. Cheon, J. S. Coron, J. Kim, M. S. Lee, T. Lepoint, M. Tibouchi, and A. Yun. Batch fully homomorphic encryption over the integers. Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 315\u2013335, 2013.","DOI":"10.1007\/978-3-642-38348-9_20"},{"key":"2025120600172418531_j_jmc-2015-0031_ref_005_w2aab3b7e1594b1b6b1ab2b1b5Aa","doi-asserted-by":"crossref","unstructured":"J. H. Cheon, K. Han, C. Lee, H. Ryu, and D. Stehl\u00e9. Cryptanalysis of the multilinear map over the integers. Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 3\u201312, 2015.","DOI":"10.1007\/978-3-662-46800-5_1"},{"key":"2025120600172418531_j_jmc-2015-0031_ref_006_w2aab3b7e1594b1b6b1ab2b1b6Aa","doi-asserted-by":"crossref","unstructured":"J. H. Cheon and D. Stehl\u00e9. Fully homomorphic encryption over the integers revisited. Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 513\u2013536, 2015.","DOI":"10.1007\/978-3-662-46800-5_20"},{"key":"2025120600172418531_j_jmc-2015-0031_ref_007_w2aab3b7e1594b1b6b1ab2b1b7Aa","doi-asserted-by":"crossref","unstructured":"J. Coron, D. Naccache, and M. Tibouchi. Public key compression and modulus switching for fully homomorphic encryption over the integers. Advances in Cryptology - EUROCRYPT, pages 446\u2013464, 2012.","DOI":"10.1007\/978-3-642-29011-4_27"},{"key":"2025120600172418531_j_jmc-2015-0031_ref_008_w2aab3b7e1594b1b6b1ab2b1b8Aa","doi-asserted-by":"crossref","unstructured":"J. S. Coron, T. Lepoint, and M. Tibouchi. Batch fully homomorphic encryption over the integers. IACR Cryptology ePrint Archive, page 36, 2013.","DOI":"10.1007\/978-3-642-54631-0_18"},{"key":"2025120600172418531_j_jmc-2015-0031_ref_009_w2aab3b7e1594b1b6b1ab2b1b9Aa","doi-asserted-by":"crossref","unstructured":"J. S. Coron, T. Lepoint, and M. Tibouchi. Practical multilinear maps over the integers. Annual Cryptology Conference, pages 476\u2013493, 2013.","DOI":"10.1007\/978-3-642-40041-4_26"},{"key":"2025120600172418531_j_jmc-2015-0031_ref_010_w2aab3b7e1594b1b6b1ab2b1c10Aa","doi-asserted-by":"crossref","unstructured":"J. S. Coron and H. V. Pereira. On kilian\u2019s randomization of multilinear map encodings. Cryptology ePrint Archive, page 1129, 2018.","DOI":"10.1007\/978-3-030-34621-8_12"},{"key":"2025120600172418531_j_jmc-2015-0031_ref_011_w2aab3b7e1594b1b6b1ab2b1c11Aa","unstructured":"T. F. development team. fplll, a lattice reduction library. Available at https:\/\/github.com\/fplll\/fplll, (2016)."},{"key":"2025120600172418531_j_jmc-2015-0031_ref_012_w2aab3b7e1594b1b6b1ab2b1c12Aa","unstructured":"J. Ding and C. Tao. A new algorithm for solving the approximate common divisor problem and cryptanalysis of the fhe based on gacd. IACR Cryptology ePrint Archive, page 42, 2014."},{"key":"2025120600172418531_j_jmc-2015-0031_ref_013_w2aab3b7e1594b1b6b1ab2b1c13Aa","doi-asserted-by":"crossref","unstructured":"S. D. Galbraith, S. W. Gebregiyorgis, and S. Murphy. Algorithms for the approximate common divisor problem. LMS J. Comput. Math., 19(A):58\u201372, 2016.","DOI":"10.1112\/S1461157016000218"},{"key":"2025120600172418531_j_jmc-2015-0031_ref_014_w2aab3b7e1594b1b6b1ab2b1c14Aa","doi-asserted-by":"crossref","unstructured":"S. Garg, C. Gentry, S. Halevi, M. Raykova, A. Sahai, and B. Waters. Candidate indistinguishability obfuscation and functional encryption for all circuits. SIAM J. Comput., 45(3):882\u2013929, 2016.","DOI":"10.1137\/14095772X"},{"key":"2025120600172418531_j_jmc-2015-0031_ref_015_w2aab3b7e1594b1b6b1ab2b1c15Aa","unstructured":"G. Hanrot, X. Pujol, and D. Stehl\u00e9. Terminating bkz. IACR Cryptology ePrint Archive, page 198, 2011."},{"key":"2025120600172418531_j_jmc-2015-0031_ref_016_w2aab3b7e1594b1b6b1ab2b1c16Aa","doi-asserted-by":"crossref","unstructured":"N. Howgrave-Graham. Approximate integer common divisors. Cryptography and lattices, pages 51\u201366, 2001.","DOI":"10.1007\/3-540-44670-2_6"},{"key":"2025120600172418531_j_jmc-2015-0031_ref_017_w2aab3b7e1594b1b6b1ab2b1c17Aa","doi-asserted-by":"crossref","unstructured":"A. K. Lenstra, H. W. Lenstra, and L. Lov\u00e1sz. Factoring polynomials with rational coefficients. Math. Ann., 261(4):515\u2013534, 1982.","DOI":"10.1007\/BF01457454"},{"key":"2025120600172418531_j_jmc-2015-0031_ref_018_w2aab3b7e1594b1b6b1ab2b1c18Aa","doi-asserted-by":"crossref","unstructured":"H. H. Nguyen and V. Vu. Random matrices: Law of the determinant. Ann. Probability, 42(1):146\u2013167, 2014.","DOI":"10.1214\/12-AOP791"},{"key":"2025120600172418531_j_jmc-2015-0031_ref_019_w2aab3b7e1594b1b6b1ab2b1c19Aa","doi-asserted-by":"crossref","unstructured":"M. Van Dijk, C. Gentry, S. Halevi, and V. Vaikuntanathan. Fully homomorphic encryption over the integers. Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 24\u201343, 2010.","DOI":"10.1007\/978-3-642-13190-5_2"}],"container-title":["Journal of Mathematical Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.degruyter.com\/view\/journals\/jmc\/14\/1\/article-p397.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2019-0031\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2019-0031\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T00:18:02Z","timestamp":1764980282000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2019-0031\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,1]]},"references-count":19,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2020,8,7]]},"published-print":{"date-parts":[[2020,8,7]]}},"alternative-id":["10.1515\/jmc-2019-0031"],"URL":"https:\/\/doi.org\/10.1515\/jmc-2019-0031","relation":{},"ISSN":["1862-2984","1862-2976"],"issn-type":[{"value":"1862-2984","type":"electronic"},{"value":"1862-2976","type":"print"}],"subject":[],"published":{"date-parts":[[2020,1,1]]}}}