Welcome to the resource topic for 2014/042
Title:
A New Algorithm for Solving the General Approximate Common Divisors Problem and Cryptanalysis of the FHE Based on the GACD problem
Authors: Jintai Ding, 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.
ePrint: https://eprint.iacr.org/2014/042
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .