Approximate Homomorphic Encryption with Reduced Approximation Error

Andrey Kim, Antonis Papadimitriou, Yuriy Polyakov

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

The Cheon-Kim-Kim-Song (CKKS) homomorphic encryption scheme is currently the most efficient method to perform approximate homomorphic computations over real and complex numbers. Although the CKKS scheme can already be used to achieve practical performance for many advanced applications, e.g., in machine learning, its broader use in practice is hindered by several major usability issues, most of which are brought about by relatively high approximation errors and the complexity of dealing with them. We present a reduced-error CKKS variant that removes the approximation errors due to the Learning With Errors (LWE) noise in the encryption and key switching operations. We propose and implement its Residue Number System (RNS) instantiation that has a lower error than the original CKKS scheme implementation based on multiprecision integer arithmetic. While formulating the RNS instantiation, we also develop an intermediate RNS variant that has a smaller approximation error than the prior RNS variant of CKKS. The high-level idea of our main RNS-related improvements is to remove the approximate scaling error using a novel procedure that computes level-specific scaling factors. The rescaling operations and scaling factor adjustments in our implementation are done automatically. We implement both RNS variants in PALISADE and compare their approximation error and efficiency to the prior RNS variant. Our results for uniform ternary secret key distribution, which is the most efficient setting included in the community homomorphic encryption security standard, show that the reduced-error CKKS RNS implementation typically has an approximation error that is 6 to 9 bits smaller for computations with multiplications than the prior RNS variant. The results for the sparse secret setting, which was used for the original CKKS scheme, imply that our reduced-error CKKS RNS implementation has an approximation error up to 12 bits smaller than the prior RNS variant.

Original languageEnglish (US)
Title of host publicationTopics in Cryptology - CT-RSA 2022 - Cryptographers’ Track at the RSA Conference, 2022, Proceedings
EditorsSteven D. Galbraith
PublisherSpringer Science and Business Media Deutschland GmbH
Pages120-144
Number of pages25
ISBN (Print)9783030953119
DOIs
StatePublished - 2022
Externally publishedYes
EventCryptographers Track at the RSA Conference, CT-RSA 2022 - Virtual, Online
Duration: Mar 1 2022Mar 2 2022

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13161 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceCryptographers Track at the RSA Conference, CT-RSA 2022
CityVirtual, Online
Period3/1/223/2/22

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Approximate Homomorphic Encryption with Reduced Approximation Error'. Together they form a unique fingerprint.

Cite this