Cryptology ePrint Archive: Report 2014/1024

Cryptanalysis of the Co-ACD Assumption

Pierre-Alain Fouque and Moon Sung Lee and Tancrède Lepoint and Mehdi Tibouchi

Abstract: At ACM-CCS 2014, Cheon, Lee and Seo introduced a new number-theoretic assumption, the co-approximate common divisor (Co-ACD) assumption, based on which they constructed several cryptographic primitives, including a particularly fast additively homomorphic encryption scheme. For their proposed parameters, they found that their scheme was the ``most efficient of those that support an additive homomorphic property''.

In this paper, we analyze the security of the Cheon-Lee-Seo (CLS) homomorphic encryption scheme and of the underlying Co-ACD assumption, and present several lattice-based attacks that are effectively devastating for the proposed constructions. First, we prove that a few known plaintexts are sufficient to decrypt any ciphertext in the symmetric-key CLS scheme. This breaks the one-wayness of both the symmetric-key and the public-key variants of CLS encryption as well as the underlying decisional Co-ACD assumption for a very wide range of parameters. Then, we show that this attack can be heuristically extended to decrypt small messages without any known plaintext. And finally, we find that Coppersmith's theorem can even be used to solve the search variant of the Co-ACD problem, and mount a full key recovery on the public-key CLS scheme.

Concretely speaking, the parameters proposed by Cheon et al. and originally aiming at 128-bit security can be broken in a matter of seconds. And while it is possible to select parameters outside of the range in which our attacks run in polynomial time, they have to be so large as to render the proposed constructions severely uncompetitive (e.g. our asymptotic estimates indicate that 128 bits of security against our attacks require a modulus of at least 400,000 bits).

Category / Keywords: Cryptanalysis, Lattice Reduction, Coppersmith Theorem, Homomorphic Encryption, Co-ACD Problem

Date: received 29 Dec 2014, last revised 12 Feb 2015

Contact author: moolee at snu ac kr

Available format(s): PDF | BibTeX Citation

Version: 20150213:011548 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]