MarriageTheoremのこと

_ 週末。

_ IACR ePrint 2014/044まで確認済み、ECCC 2003年分まで確認済み

_ 気になった論文：A New Algorithm for Solving the Approximate Common Divisor Problem and Cryptanalysis of the FHE based on GACD, Jintai Ding, Chengdong Tao, http://eprint.iacr.org/2014/042

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$.