ICICS 2022: New Results of Breaking the CLS Scheme from ACM-CCS 2014

Authors: Jing Gao, Jun Xu, Tianyu Wang and Lei Hu Abstract: At ACM-CCS 2014, Cheon, Lee and Seo introduced a particularly fast additively homomorphic encryption scheme (CLS scheme) based on a new number theoretic assumption, the co-Approximate Common Divisor (co-ACD) assumption. However, at Crypto 2015, Fouque et al. presented several lattice-based attacks that effectively devastated this scheme. They proved that a few known plaintexts are sufficient to break both the symmetric-key and the public-key variants, and they gave a heuristic lattice method for solving the search co-ACD problem. In this paper, we mainly improve in terms of the number of samples, and propose a new key-retrieval attack. We first give an effective attack by Coppersmith’s method to break the co-ACD problem with N=p1⋯pn is known. If n is within a certain range, our work is theoretically valid for a wider range of parameters. When n=2, we can successfully solve it with only two samples, that is the smallest number of needed samples to the best of our knowledge. A known plaintext attack on the CLS scheme can be simply converted to solving the co-ACD problem with a known N, again requiring fewer samples than before to retrieve the private key. Finally, we show a ciphertext-only attack with a hybrid approach of direct lattice and Coppersmith’s method that can recover the key with a smaller number of ciphertexts and without any restriction on the plaintext size, but N is needed. All of our attacks are heuristic, but we have experimentally verified that these attacks work efficiently for the parameters proposed in the CLS scheme, which can be broken in seconds by experiments. To read more about the paper, please visit: https://link.springer.com/chapter/10.1007/978-3-031-15777-6_3 To read other papers at ICICS 2022, please visit: https://icics2022.cyber.kent.ac.uk/program.php or https://link.springer.com/book/9783031157769