EvalRound+ Bootstrapping and its Rigorous Analysis for CKKS Scheme

Hyewon Sung; Sieun Seo; Taekyung Kim; Chohong Min

Paper 2024/1379

EvalRound+ Bootstrapping and its Rigorous Analysis for CKKS Scheme

Hyewon Sung

, Ewha Womans University

Sieun Seo

, Ewha Womans University

Taekyung Kim

, CryptoLab. Inc.

Chohong Min

, Ewha Womans University

Abstract

Bootstrapping stands as a fundamental component of fully homomorphic encryption (FHE) schemes, facilitating an infinite number of operations by recovering the ciphertext modulus. This work is aimed at significantly reducing the consumption of modulus in bootstrapping, thereby enhancing the efficiency of FHE performance, specifically for the Cheon--Kim--Kim--Song (CKKS) scheme proposed by Cheon et al. Building on the EvalRound bootstrapping method proposed by Kim et al., which includes the steps of ModRaise, CoeffToSlot, EvalRound and SlotToCoeff, we introduce bootstrapping. This bootstrapping inherits the advantage of EvalRound bootstrapping in CoeffToSlot and resolves its disadvantage in SlotToCoeff. Furthermore, we conduct a set of rigorous and comprehensive analyses to precisely determine the optimal choices of the parameters. The implementation of bootstrapping, along with optimal choices, has achieved a reduction in modulus consumption by over for CoeffToSlot and SlotToCoeff. Additionally, it has increased the number of levels for general multiplication by 2-4 in the most widely used bootstrapping parameter sets.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: Fully Homomorphic Encryption Bootstrapping CKKS
Contact author(s): hyewonsung @ ewha ac kr
sieun1114 @ ewha ac kr
taekyung kim @ cryptolab co kr
chohong @ ewha ac kr
History: 2024-09-04: approved; 2024-09-03: received; See all versions
Short URL: https://ia.cr/2024/1379
License: CC BY

BibTeX

@misc{cryptoeprint:2024/1379,
      author = {Hyewon Sung and Sieun Seo and Taekyung Kim and Chohong Min},
      title = {{EvalRound}+ Bootstrapping and its Rigorous Analysis for {CKKS} Scheme},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1379},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1379}
}