Paper 2014/042
A New Algorithm for Solving the General Approximate Common Divisors Problem and Cryptanalysis of the FHE Based on the GACD problem
Jintai Ding and 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
Metadata
- Available format(s)
-
PDF
- Publication info
- Preprint. MINOR revision.
- Keywords
- General approximate common divisors problemsFully homomorphic encryptionLatticeLLLBKZHermite Factor
- 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
BibTeX
@misc{cryptoeprint:2014/042, author = {Jintai Ding and Chengdong Tao}, title = {A New Algorithm for Solving the General Approximate Common Divisors Problem and Cryptanalysis of the {FHE} Based on the {GACD} problem}, howpublished = {Cryptology {ePrint} Archive, Paper 2014/042}, year = {2014}, url = {https://eprint.iacr.org/2014/042} }