TY - GEN
T1 - EvalRound Algorithm in CKKS Bootstrapping
AU - Kim, Seonghak
AU - Park, Minji
AU - Kim, Jaehyung
AU - Kim, Taekyung
AU - Min, Chohong
N1 - Funding Information:
Acknowledgements. The research was supported by Basic Science Research Program through the National Research Foundation of Korea(NRF) funded by the Ministry of Education (Grant No. 2019R1A6A1A11051177 and 2021R1A2C1095703) and Institute of Information & Communications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) [NO.2022-0-01047, Development of statistical analysis algorithm and module using homomorphic encryption based on real number operation].
Publisher Copyright:
© 2022, International Association for Cryptologic Research.
PY - 2022
Y1 - 2022
N2 - Homomorphic encryption (HE) has opened an entirely new world up in the privacy-preserving use of sensitive data by conducting computations on encrypted data. Amongst many HE schemes targeting computation in various contexts, Cheon–Kim–Kim–Song (CKKS) scheme [8] is distinguished since it allows computations for encrypted real number data, which have greater impact in real-world applications. CKKS scheme is a levelled homomorphic encryption scheme, consuming one level for each homomorphic multiplication. When the level runs out, a special computational circuit called bootstrapping is required in order to conduct further multiplications. The algorithm proposed by Cheon et al. [7] has been regarded as a standard way to do bootstrapping in the CKKS scheme, and it consists of the following four steps: ModRaise, CoeffToSlot, EvalMod and SlotToCoeff. However, the steps consume a number of levels themselves, and thus optimizing this extra consumption has been a major focus of the series of recent research. Among the total levels consumed in the bootstrapping steps, about a half of them is spent in CoeffToSlot and SlotToCoeff steps to scale up the real number components of DFT matrices and round them to the nearest integers. Each scale-up factor is very large so that it takes up one level to rescale it down. Scale-up factors can be taken smaller to save levels, but the error of rounding would be transmitted to EvalMod and eventually corrupt the accuracy of bootstrapping. EvalMod aims to get rid of the superfluous qI term from a plaintext pt+ qI resulting from ModRaise, where q is the bottom modulus and I is a polynomial with small integer coefficients. EvalRound is referred to as its opposite, obtaining qI. We introduce a novel bootstrapping algorithm consisting of ModRaise, CoeffToSlot, EvalRound and SlotToCoeff, which yields taking smaller scale-up factors without the damage of rounding errors.
AB - Homomorphic encryption (HE) has opened an entirely new world up in the privacy-preserving use of sensitive data by conducting computations on encrypted data. Amongst many HE schemes targeting computation in various contexts, Cheon–Kim–Kim–Song (CKKS) scheme [8] is distinguished since it allows computations for encrypted real number data, which have greater impact in real-world applications. CKKS scheme is a levelled homomorphic encryption scheme, consuming one level for each homomorphic multiplication. When the level runs out, a special computational circuit called bootstrapping is required in order to conduct further multiplications. The algorithm proposed by Cheon et al. [7] has been regarded as a standard way to do bootstrapping in the CKKS scheme, and it consists of the following four steps: ModRaise, CoeffToSlot, EvalMod and SlotToCoeff. However, the steps consume a number of levels themselves, and thus optimizing this extra consumption has been a major focus of the series of recent research. Among the total levels consumed in the bootstrapping steps, about a half of them is spent in CoeffToSlot and SlotToCoeff steps to scale up the real number components of DFT matrices and round them to the nearest integers. Each scale-up factor is very large so that it takes up one level to rescale it down. Scale-up factors can be taken smaller to save levels, but the error of rounding would be transmitted to EvalMod and eventually corrupt the accuracy of bootstrapping. EvalMod aims to get rid of the superfluous qI term from a plaintext pt+ qI resulting from ModRaise, where q is the bottom modulus and I is a polynomial with small integer coefficients. EvalRound is referred to as its opposite, obtaining qI. We introduce a novel bootstrapping algorithm consisting of ModRaise, CoeffToSlot, EvalRound and SlotToCoeff, which yields taking smaller scale-up factors without the damage of rounding errors.
KW - Bootstrapping
KW - CKKS scheme
KW - Homomorphic encryption
UR - http://www.scopus.com/inward/record.url?scp=85148045458&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-22966-4_6
DO - 10.1007/978-3-031-22966-4_6
M3 - Conference contribution
AN - SCOPUS:85148045458
SN - 9783031229657
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 161
EP - 187
BT - Advances in Cryptology – ASIACRYPT 2022 - 28th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
A2 - Agrawal, Shweta
A2 - Lin, Dongdai
PB - Springer Science and Business Media Deutschland GmbH
T2 - 28th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2022
Y2 - 5 December 2022 through 9 December 2022
ER -