**Algorithms for CRT-variant of Approximate Greatest Common Divisor Problem**

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

**Abstract: **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.

**Category / Keywords: **CCK-ACD; Lattice; orthogonal lattice attack; SDA

**Date: **received 19 Feb 2019, last revised 26 Feb 2019

**Contact author: **changmin lee at ens-lyon fr,tory154@snu ac kr,wony0404@snu ac kr,hhan_@snu ac kr

**Available format(s): **PDF | BibTeX Citation

**Version: **20190227:024644 (All versions of this report)

**Short URL: **ia.cr/2019/195

[ Cryptology ePrint archive ]