Welcome to the resource topic for 2024/853
Title:
Practical q-IND-CPA-D-Secure Approximate Homomorphic Encryption
Authors: Jean-Philippe Bossuat, Anamaria Costache, Christian Mouchet, Lea Nürnberger, Juan Ramón Troncoso-Pastoriza
Abstract:At Eurocrypt 2021, Li and Micciancio demonstrated that the IND-CPA notion of security is not sufficient to cover the passive security of approximate homomorphic encryption schemes, by outlining a key recovery attack against the CKKS scheme (Cheon, Kim, Kim, Seong, Asiacrypt 2017). They proposed the notion of q-IND-CPA-D security, which allows an adversary to make q calls to a restricted decryption oracle. Li and Micciancio left achieving q-IND-CPA-D security as an open problem, but proposed two approaches: noise flooding and an exact version of CKKS.
The first approach was addressed by Li, Micciancio, Schultz and Sorrell (Crypto 2022), but leads to substantial efficiency loss.
In this work, we look at the second approach.
We define (\delta, r)-exact CKKS, a version of CKKS that returns exact results on all except the least r significant bits with (high) probability \delta, based on bounds on the noise. We prove that the advantage of a q-IND-CPA-D attacker against (\delta, r)-exact CKKS is determined by the failure probability of those bounds. We conduct a tight average-case and implementation-specific noise analysis of all elementary operations in CKKS, as implemented in the Lattigo library, including the bootstrapping operation. We propose bounds that have small enough failure probability for the advantage of a q-IND-CPA-D attacker against (\delta,r)-exact CKKS to become smaller than 2^{-128}, while the parameter sets needed remain practical. We furthermore present an estimator tool that combines the bounds on basic operations and returns tight noise estimates, even for large circuits. We validate our bounds by showcasing experimental results on different iterative algorithms, homomorphic encoding, decoding and bootstrapping.
ePrint: https://eprint.iacr.org/2024/853
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .