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 $3/4$-th root of that of exhaustive search. Interestingly, our main technique can also be applied to other settings, such as noisy factoring and attacking low-exponent RSA.

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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2011/436}},
      url = {https://eprint.iacr.org/2011/436}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.