Cryptology ePrint Archive: Report 2020/1533

On the Security of Homomorphic Encryption on Approximate Numbers

Baiyu Li and Daniele Micciancio

Abstract: We present passive attacks against CKKS, the homomorphic encryption scheme for arithmetic on approximate numbers presented at Asiacrypt 2017. The attack is both theoretically efficient (running in expected polynomial time) and very practical, leading to complete key recovery with high probability and very modest running times. We implemented and tested the attack against 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 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