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)
- 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
-
CC BY