Cryptanalysis of the Co-ACD Assumption

摘要

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". Unfortunately, it turns out that those parameters, originally aiming at 128-bit security, can be broken in a matter of seconds. Indeed, this paper presents several lattice-based attacks against the Cheon-Lee-Seo (CLS) homomorphic encryption scheme and of the underlying Co-ACD assumption that are effectively devastating for the proposed constructions. A few known plaintexts are sufficient to decrypt any ciphertext in the symmetric-key CLS scheme, and small messages can even be decrypted without any known plaintext at all. This breaks the security of both the symmetric-key and the public-key variants of CLS encryption as well as the underlying decisional Co-ACD assumption. Moreover, Coppersmith techniques can be used to solve the search variant of the Co-ACD problem and mount a full key recovery on the CLS scheme.