Making CKKS More Secure

Up to now most applications of homomorphic encryption have used a security model based on the concept of INDistinguishability under the Chosen Plaintext Attack (IND-CPA). This security model has previously been widely used and originally formulated for (non-homomorphic) public key encryption.  In this model the adversary is tasked with distinguishing between the encryptions of two (adversarially chosen) messages m₀ and m₁. If no adversary can efficiently tell apart an encryption of m₀ from an encryption of m₁, given the scheme public key, then the scheme is deemed secure.

The IND-CPA notion applies well to homomorphic encryption because any additional information typically available to an adversary attacking such a scheme (e.g., encryptions of additional messages, results of homomorphic computations, etc.) can be computed by the adversary on its own using the public key material. Because of this, the additional information does not increase the adversary’s powers. This is well established for encryption schemes satisfying standard correctness properties, and most homomorphic encryption schemes can be proven to satisfy IND-CPA security based on the Learning With Errors (LWE) hardness assumption.

Prof. Daniele Micciancio from UCSD, who is also a consultant for Duality, and his PhD student Baiyu Li recently observed (https://eprint.iacr.org/2020/1533) that the IND-CPA model may not be strong enough for some special practical applications, when the homomorphic encryption only satisfies an approximate correctness condition.  Their main observation is that a decryption result in approximate homomorphic encryption, such as for the Cheon-Kim-Kim-Song (CKKS) scheme, leaks information about the LWE noise in the approximation error.  This noise can be used to recover the underlying secret key.  CKKS is implemented in the major open source homomorphic encryption libraries, including PALISADE.  This result is not relevant to all homomorphic encryption schemes.  We have developed an enhancement to the CKKS scheme we implemented in PALISADE which addresses this observation.

The practical scenarios where the IND-CPA model is insufficient for approximate encryption schemes, such as CKKS, are the use cases where the decryption results need to be published, or shared with anybody  not completely trusted. One representative use case is where multiple data providers send the data encrypted under a common public key to the computation host, and want to receive a model computed using the joined data sets. Here, if an approximate encryption scheme is used without appropriate protective enhancements, a data owner, given the (unencrypted) model, may be able to recover the scheme secret key, and then fully decrypt the data sets that belong to other data owners.

Beside drawing attention to this security issue affecting CKKS, Li and Micciancio also introduced stronger adversarial models, namely bounded and unbounded IND-CPA+, which extend the IND-CPA model to capture these use cases of approximate homomorphic encryption. They described two main techniques to achieve stronger models for CKKS: adding Gaussian noise and rounding. Li and Micciancio also demonstrated that the IND-CPA and IND-CPA+ models are equivalent for exact homomorphic encryption schemes. So, as long as the encryption scheme provides an exact decryption algorithm, it is safe to keep using the standard notion of IND-CPA security.

Shortly after being told of the latest results we describe above, the PALISADE team formulated a practical extension of CKKS based on Gaussian noise and implemented it in PALISADE v1.10.6.  This version of PALISADE with the protective enhancement was released before the result from Daniele Micciancio and Baiyu Li was published or publicly known. This extension was jointly developed and examined by Yuriy Polyakov, Baiyu Li, and Daniele Micciancio, and then experimentally tested by Baiyu Li against the practical attacks presented in their paper (https://eprint.iacr.org/2020/1533). The results of the new tests are summarized in the Responsible Disclosure section of the paper, and show that the original attacks are not effective against the revised CKKS scheme. Other homomorphic encryption schemes implemented in the PALISADE library have an exact decryption algorithm, and are not affected by these attacks.

The PALISADE team also shared their solution with the other major open source homomorphic encryption library developers and led the homomorphic encryption community effort in extending the CKKS scheme as part of our commitment to open source distribution of privacy tools. Currently, several homomorphic encryption libraries provide an implementation of the extended CKKS scheme.