Cryptology ePrint Archive: Report 2014/042

A New Algorithm for Solving the Approximate Common Divisor Problem and Cryptanalysis of the FHE based on GACD

Jintai Ding, Chengdong Tao

Abstract: In this paper, we propose a new algorithm for solving the approximate common divisors problems, which is based on LLL reduction algorithm of certain special lattice and linear equation solving algorithm over integers. Through both theoretical argument and experimental data, we show that our new algorithm is a polynomial time algorithm under reasonable assumptions on the parameters. We use our algorithm to solve concrete problems that no other algorithm could solve before. Further more, we show that our algorithm can break the fully homomorphic encryption schemes, which are based on the approximate common divisors problem, in polynomial time in terms of the system parameter $\lambda$.

Category / Keywords: public-key cryptography / GACD, LLL, FHE, Cryptanalysis

Date: received 16 Jan 2014

Contact author: jintai ding at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20140117:095533 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]