The attack shows that the traditional formulation of IND-CPA 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 propose both indistinguishability-based and simulation-based variants, as well as restricted versions of the definitions that limit the order and number of adversarial queries (as may be enforced by some applications). We prove implications and separations among different definitional variants, and discuss possible modifications to CKKS that may serve as a countermeasure to our attacks.
Category / Keywords: public-key cryptography / homomorphic encryption, approximate encryption, passive security, Date: received 7 Dec 2020, last revised 5 Jan 2021 Contact author: baiyu at cs ucsd edu Available format(s): PDF | BibTeX Citation Note: Revised Theorem 2 and updated Acknowledgement. Version: 20210106:015318 (All versions of this report) Short URL: ia.cr/2020/1533