Paper 2019/195

Algorithms for CRT-variant of Approximate Greatest Common Divisor Problem

Jung Hee Cheon, Wonhee Cho, Minki Hhan, Minsik Kang, Jiseung Kim, and Changmin Lee


The approximate greatest common divisor problem (ACD) and its variants have been used to construct many cryptographic primitives. In particular, variants of the ACD problem based on Chinese remainder theorem (CRT) are exploited 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 to solve its security foundation have not been studied well compared to the original ACD based scheme. In this paper, we propose two algorithms for solving the CCK-ACD problem, which is used to construct a batch fully homomorphic encryption over integers. To achieve the goal, we revisit the orthogonal lattice attack and simultaneous Diophantine approximation algorithm. Both two algorithms take the same time complexity $2^{\tilde{O}(\frac{\gamma}{(\eta-\rho)^2})}$ up to a polynomial factor to solve the CCK-ACD problem for the bit size of samples $\gamma$, secret primes $\eta$, and error bound $\rho$. Compared to Chen and Nguyen's algorithm in Eurocrypt' 12, which takes $\tilde{O}(2^{\rho/2})$ complexity, our algorithm gives the first parameter condition related to $\eta$ and $\gamma$ size. We also report the experimental results for our attack upon several parameters. From the results, we can see that our algorithms work well both in theoretical and experimental terms.

Available format(s)
Publication info
Preprint. MINOR revision.
CCK-ACDLatticeorthogonal lattice attackSDA
Contact author(s)
changmin lee @ ens-lyon fr
tory154 @ snu ac kr
wony0404 @ snu ac kr
hhan_ @ snu ac kr
2019-02-27: received
Short URL
Creative Commons Attribution


      author = {Jung Hee Cheon and Wonhee Cho and Minki Hhan and Minsik Kang and Jiseung Kim and Changmin Lee},
      title = {Algorithms for CRT-variant of Approximate Greatest Common Divisor Problem},
      howpublished = {Cryptology ePrint Archive, Paper 2019/195},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.