We present passive attacks against CKKS, the homomorphic encryption scheme for arithmetic on approximate numbers presented at Asiacrypt 2017. The attacks are both theoretically efficient (running in expected polynomial time) and very practical, leading to complete key recovery with high probability and very modest running times. The attacks have been implemented and tested against all major open source homomorphic encryption libraries, including HEAAN, SEAL, HElib and PALISADE, and when computing several functions that often arise in applications of the CKKS scheme to machine learning on encrypted data, like mean and variance computations, and approximation of logistic and exponential functions using their Maclaurin series.
The attack shows that the traditional formulation of INDCPA security (or indistinguishability against chosen plaintext attacks) achieved by CKKS does not adequately capture security against passive adversaries when applied to approximate encryption schemes, and that a different, stronger definition is required to evaluate the security of such schemes. We provide a solid theoretical basis for the security evaluation of homomorphic encryption on approximate numbers (against passive attacks) by proposing new definitions, that naturally extend the traditional notion of INDCPA security to the approximate computation setting. We then discuss implications and separations among different definitional variants, and possible methods to modify the CKKS to avoid our attack and provably achieve our stronger security definition.
Daniele Micciancio received his PhD in Computer Science from MIT in 1998, and in 1999 he joined the faculty of the Computer Science and Engineering department at UC San Diego, where he has been a full professor since 2009. He has worked in many areas of theoretical computer science and cryptography, but he is most known for his pioneering work on the foundations of lattice based cryptography. Among his best known results are the proof that the Shortest Vector Problem in NP-hard to approximate within some constant factor (FOCS1998), the first (deterministic) single exponential time algorithm to solve the closest vector problem (with Voulgaris, STOC 2010), and the development of Gaussian techniques for the analysis of lattice cryptography (with Regev, FOCS 2004). But the result that he is most proud of is the first efficient cryptographic construction provably secure based on the worst case hardness of algebraic lattices (FOCS 2002), which opened the door to the development of efficient lattice based cryptography, including the design of the SWIFFT hash function (with Lyubashevsky, Peikert and Rosen, FSE 2008), and the FHEW fully homomorphic encryption scheme (with Ducas, Eurocrypt 2015). His work has been recognized by several awards, including the Matchey best paper award (FOCS 1998), Sprowls PhD thesis award (1999), NSF CAREER award (2001), Hellman fellowship (2001), and Alfred P. Sloan Fellowship (2003). He was invited speaker at PKC 2010 and Eurocrypt 2019, and Beeger lecturer at the Netherland math congress in 2014. He served as program chair of TCC 2010, Crypto 2019 and Crypto 2020, general chair of TCC 2014, and associate editor of Information and Computation, SIAM J. on Computing and the Journal of Cryptology. In 2019 he was named Fellow of the International Association of Cryptologic Research for his many research and service contributions.