Securing Approximate Homomorphic Encryption Using Differential Privacy
Securing Approximate Homomorphic Encryption Using Differential Privacy
复制标题
DOI：
10.1007/978-3-031-15802-5_20
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Baiyu Li;D. Micciancio;Mark Schultz;Jessica Sorrell
中科院分区：
文献类型：
--
作者：
Baiyu Li;D. Micciancio;Mark Schultz;Jessica Sorrell
Li和Micciancio（Eurocrypt 2021）的最新工作表明，选择明文攻击下的不可验证性的传统公式（）不足以捕获近似同态加密对被动对手的安全性，并确定了一个更强的安全性定义（解密预言机）作为近似加密方案的适当安全目标。我们展示了如何将任何近似同态加密方案实现weaksecurity定义，到一个可证明是安全的，对现实的被动攻击提供强有力的保证。该方法的工作原理是对解密函数的输出进行后处理，并采用一种满足差分隐私（DP）概念的机制，根据同态计算的最坏情况误差增长量添加一定量的噪声，我们将这些结果应用于Cheon，Kim，Kim和Song的近似同态加密方案（CKKS，Asiacrypt 2017），证明将高斯噪声添加到CKKS解密的输出中足以确保安全性。我们通过证明几乎匹配的上限和下限来精确地量化必须添加多少高斯噪声，这表明人们不能希望显着减少在此后处理步骤中添加的噪声量。作为一个额外的贡献，我们提出并使用一个更细粒度的比特安全性的定义，区分计算安全参数（C）和统计的（S）。基于我们的上限和下限，我们提出了参数的反措施最近通过的开源库实现CKKS.Finally，我们调查了合理的说法，较小的DP噪声参数可能足以确保安全的方案支持更准确的（动态的，密钥相关的）估计密文噪声在解密过程中。也许令人惊讶的是，我们表明，这种说法是错误的，和DP机制与噪声参数定制的错误存在于一个给定的密文，而不是最坏情况下的错误，是容易受到攻击。
Recent work of Li and Micciancio (Eurocrypt 2021) has shown that the traditional formulation ofindistinguishability under chosen plaintext attack() is not adequate to capture the security ofapproximatehomomorphic encryption against passive adversaries, and identified a strongersecurity definition (with decryption oracles) as the appropriate security target for approximate encryption schemes. We show how to transform any approximate homomorphic encryption scheme achieving the weaksecurity definition, into one which is provablysecure, offering strong guarantees against realistic passive attacks. The method works by postprocessing the output of the decryption function with a mechanism satisfying an appropriate notion ofdifferential privacy (DP), adding an amount of noise tailored to the worst-case error growth of the homomorphic computation.We apply these results to the approximate homomorphic encryption scheme of Cheon, Kim, Kim, and Song (CKKS, Asiacrypt 2017), proving that adding Gaussian noise to the output of CKKS decryption suffices to achievesecurity. We precisely quantify how much Gaussian noise must be added by proving nearly matching upper and lower bounds, showing that one cannot hope to significantly reduce the amount of noise added in this post-processing step. As an additional contribution, we present and use a finer grained definition of bit security that distinguishes between a computational security parameter (c) and a statistical one (s). Based on our upper and lower bounds, we propose parameters for the counter-measures recently adopted by open-source libraries implementing CKKS.Lastly, we investigate the plausible claim that smaller DP noise parameters might suffice to achieve-security for schemes supporting more accurate (dynamic, key dependent) estimates of ciphertext noise during decryption. Perhaps surprisingly, we show that this claim is false, and that DP mechanisms with noise parameters tailored to the error present in a given ciphertext, rather than worst-case error, are vulnerable toattacks.