### 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.

Note: Changed the name of the proposed security notion to IND-CPA^D to clearly indicate that decryption results are revealed to adversary, and made a few updates to explain when the attack could happen.

Available format(s)
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in EUROCRYPT 2021
Keywords
homomorphic encryptionapproximate encryptionpassive security
Contact author(s)
baiyu @ cs ucsd edu
History
2021-03-07: last of 2 revisions
See all versions
Short URL
https://ia.cr/2020/1533

CC BY

BibTeX

@misc{cryptoeprint:2020/1533,
author = {Baiyu Li and Daniele Micciancio},
title = {On the Security of Homomorphic Encryption on Approximate Numbers},
howpublished = {Cryptology ePrint Archive, Paper 2020/1533},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/1533}},
url = {https://eprint.iacr.org/2020/1533}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.