Paper 2014/042

A New Algorithm for Solving the General Approximate Common Divisors Problem and Cryptanalysis of the FHE Based on the GACD problem

Jintai Ding and Chengdong Tao

Abstract

In this paper, we propose a new algorithm for solving the general approximate common divisors (GACD) problems, which is based on lattice reduction algorithms on certain special lattices and linear equation solving algorithms over integers. Through both theoretical arguments and experimental data, we show that our new algorithm works in polynomial time but under roughly the following condition: \begin{itemize} \item There is a positive integer $t$ such that $$\frac{\gamma+\eta}{t} + \frac{t}{H}+\rho < \eta;$$ \item We have more than $t$ GACD samples. \end{itemize} or equivalently \begin{itemize} \item $$H(\eta-\rho)^{2}-4(\gamma+\eta)>0$$ \item We have more than $t=\lceil\frac{H(\eta-\rho)-\sqrt{H^{2}(\eta-\rho)^{2}-4H(\gamma+\eta)}}{2}\rceil$ GACD samples. \end{itemize} Here $\gamma$, $\eta$ and $\rho$ are parameters describing a GACD problem, $H =1/ \log_{2}F$ and $F$ is the Hermite Factor. In our experiments, $H$ is shown to be roughly $40$ when using the LLL reduction algorithm and it should be around $80$ when using Deep or BKZ algorithms. % We use our algorithm to solve concrete problems that no other algorithm could solve before. We show how our algorithm can be applied to attack the fully homomorphic encryption schemes which are based on the general approximate common divisors problem and its limitations.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
General approximate common divisors problemsFully homomorphic encryptionLatticeLLLBKZHermite Factor
Contact author(s)
jintai ding @ gmail com
History
2014-03-03: last of 2 revisions
2014-01-17: received
See all versions
Short URL
https://ia.cr/2014/042
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/042,
      author = {Jintai Ding and Chengdong Tao},
      title = {A New Algorithm for Solving the General Approximate Common Divisors Problem and Cryptanalysis of the FHE Based on the GACD problem},
      howpublished = {Cryptology ePrint Archive, Paper 2014/042},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/042}},
      url = {https://eprint.iacr.org/2014/042}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.