Paper 2014/1024

Cryptanalysis of the Co-ACD Assumption

Pierre-Alain Fouque, Moon Sung Lee, 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).