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: ia.cr/2014/1024 Discussion forum: Show discussion | Start new discussion