Paper 2022/162

On the precision loss in approximate homomorphic encryption

Anamaria Costache, Benjamin R. Curtis, Erin Hales, Sean Murphy, Tabitha Ogilvie, and Rachel Player

Abstract

Since its introduction at Asiacrypt 2017, the CKKS approximate homomorphic encryption scheme has become one of the most widely used and implemented homomorphic encryption schemes. Due to the approximate nature of the scheme, application developers using CKKS must ensure that the evaluation output is within a tolerable error of the corresponding cleartext computation. This is achieved by scaling the underlying raw data by an appropriate amount, known as the scale parameter, in order to preserve a certain amount of significant figures. Unfortunately, there is no clear guidance available for choosing an appro- priate scale parameter, with a trial-and-error approach typically advised. In this work, we significantly improve the state-of-affairs and present the following main contributions. We give a comprehensive theoretical and experimental analysis of CKKS noise, that considers noise coming from the encoding and homomorphic evaluation operations separately. This enables us to give the first explicit definition for precision in the CKKS context. Additionally, we demonstrate the applicability of our analysis to determine convergence properties of iterative algorithms that are commonly used in applications.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
approximate encryptionfully homomorphic encryptionlattice-based cryptography
Contact author(s)
anamaria costache @ ntnu no
ben curtis @ zama ai
erin hales 2018 @ live rhul ac uk
s murphy @ rhul ac uk
tabitha ogilvie 2019 @ live rhul ac uk
rachel player @ rhul ac uk
History
2022-02-20: received
Short URL
https://ia.cr/2022/162
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/162,
      author = {Anamaria Costache and Benjamin R.  Curtis and Erin Hales and Sean Murphy and Tabitha Ogilvie and Rachel Player},
      title = {On the precision loss in approximate homomorphic encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2022/162},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/162}},
      url = {https://eprint.iacr.org/2022/162}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.