Skip to Main content Skip to Navigation
Conference papers

Faster Algorithms for Approximate Common Divisors: Breaking Fully-Homomorphic-Encryption Challenges over the Integers

Yuanmi Chen 1 Phong Q. Nguyen 2, 3
3 CRYPT - Cryptanalyse
LIAMA - Laboratoire Franco-Chinois d'Informatique, d'Automatique et de Mathématiques Appliquées, Inria Paris-Rocquencourt
Abstract : At EUROCRYPT '10, van Dijk et al. 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 et al. at CRYPTO '11 to build a more efficient variant of the FHE scheme by van Dijk 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 et al. Our PACD algorithm directly gives rise to a new GACD algorithm, which is exponentially faster than exhaustive search. Interestingly, our main technique can also be applied to other settings, such as noisy factoring and attacking low-exponent RSA.
Document type :
Conference papers
Complete list of metadata

Cited literature [26 references]  Display  Hide  Download

https://hal.inria.fr/hal-00864374
Contributor : Phong Q. Nguyen <>
Submitted on : Saturday, September 21, 2013 - 9:09:27 AM
Last modification on : Thursday, July 1, 2021 - 5:32:25 PM
Long-term archiving on: : Friday, April 7, 2017 - 12:52:26 AM

File

ChenNguyen.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Yuanmi Chen, Phong Q. Nguyen. Faster Algorithms for Approximate Common Divisors: Breaking Fully-Homomorphic-Encryption Challenges over the Integers. EUROCRYPT 2012, IACR, Apr 2012, Cambridge, United Kingdom. pp.502-519, ⟨10.1007/978-3-642-29011-4_30⟩. ⟨hal-00864374⟩

Share

Metrics

Record views

1001

Files downloads

1098