Cryptology ePrint Archive: Report 2022/162

On the precision loss in approximate homomorphic encryption

Anamaria Costache and Benjamin R. Curtis and Erin Hales and Sean Murphy and 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.

Category / Keywords: approximate encryption, fully homomorphic encryption, lattice-based cryptography

Date: received 12 Feb 2022

Contact author: anamaria costache at ntnu no, ben curtis at zama ai, erin hales 2018 at live rhul ac uk, s murphy at rhul ac uk, tabitha ogilvie 2019 at live rhul ac uk, rachel player at rhul ac uk

Available format(s): PDF | BibTeX Citation

Version: 20220220:200321 (All versions of this report)

Short URL: ia.cr/2022/162


[ Cryptology ePrint archive ]