You are looking at a specific version 20140117:095533 of this paper. See the latest version.

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

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
GACDLLLFHECryptanalysis
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
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.