Paper 2011/436
Faster Algorithms for Approximate Common Divisors: Breaking Fully-Homomorphic-Encryption Challenges over the Integers
Yuanmi Chen and Phong Q. Nguyen
Abstract
At EUROCRYPT '10, van Dijk, Gentry, Halevi and Vaikuntanathan presented simple fully-homomorphic encryption (FHE) schemes
based on the hardness of approximate integer common divisors problems,
which were introduced in 2001 by Howgrave-Graham.
There are two versions for these problems: the partial version (PACD) and the general version (GACD).
The seemingly easier problem PACD was recently used by Coron, Mandal, Naccache and Tibouchi at CRYPTO '11 to build a more efficient variant of the FHE scheme
by van Dijk {\em et al.}. We present a new PACD algorithm whose running time is essentially the ``square root''
of that of exhaustive search, which was the best attack in practice. This allows us to experimentally break the FHE challenges proposed by Coron {\em et al.}
Our PACD algorithm directly gives rise to a new GACD algorithm, which is exponentially faster than exhaustive search:
namely, the running time is essentially the
Note: This is the full version of EUROCRYPT '12.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. This is the full version of EUROCRYPT '12.
- Keywords
- fully-homomorphic encryptioncryptanalysis
- Contact author(s)
- pnguyen @ di ens fr
- History
- 2012-07-20: last of 2 revisions
- 2011-08-12: received
- See all versions
- Short URL
- https://ia.cr/2011/436
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2011/436, author = {Yuanmi Chen and Phong Q. Nguyen}, title = {Faster Algorithms for Approximate Common Divisors: Breaking Fully-Homomorphic-Encryption Challenges over the Integers}, howpublished = {Cryptology {ePrint} Archive, Paper 2011/436}, year = {2011}, url = {https://eprint.iacr.org/2011/436} }