Precision Beyond the Limit: Meta-BTS Bootstrapping
Explore the innovative Meta-BTS Bootstrapping technique that pushes precision limits in homomorphic encryption, allowing efficient computation over encrypted data without decryption. Learn about the challenges and strategies for achieving high precision in privacy-preserving computation.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
META-BTS: Bootstrapping Precision Beyond the Limit WONHEE CHO1 Joint work with Jung Hee Cheon1,2, Youngjin Bae2, Jaehyung Kim2 and Taekyung Kim2 1Seoul National University and 2CryptoLab. Inc. 2022. 10. 19 1
Outline Homomorphic Encryption CKKS scheme Bootstrapping for CKKS META-BTS 2
Homomorphic Encryption ? Circuit ? ?(?) c?(?) c?(?(?)) Encryption scheme which allows computing over encrypted data without decryption Provides efficient privacy preserving computation 3
CKKS scheme 3 + 5 = 8 .2 .3 .3 Encrypt Decrypt Encrypt 3 = + 5 8 .3 .2 .1 Provides approximate computation Supports SIMD addition and multiplication on complex numbers 4 [CKKS17] Jung Hee Cheon et.al. Homomorphic Encryption for Arithmetic of Approximate Numbers. Asiacrypt 2017
Homomorphic Encryption ? ????? Capacity of ciphertext ? 1 ????? Message Bootstrapping (BTS) Error 0 ????? Multiplication of ciphertexts consumes level(modulus) To continue homomorphic computations, need to refresh 5
Bootstrapping (BTS) EvalMod ModRaise (??? ?) (??? ?) (??? ?) Homomorphic re-encryption of a ciphertext Capacity of ciphertext Message Requiring a complicated combination of homomorphic operations Error Bottleneck of HE application ?? Needs a lot of time Error(BTS) Hard to obtain high precision 6
Bootstrapping (BTS) Measures of BTS efficiency More mult. Level after BTS Less time consuming (level)/(BTS time) can be a rough efficiency of BTS with fixed precision Hard to achieve high precision after BTS 7
The Limit - BTS precision Bootstrapping itself consumes modulus (level) Limitation of ciphertext modulus with fixed ciphertext polynomial dimension N To achieve high precision, uses more levels during BTS Higher degree polynomial approximation BTS (low prec.) BTS (high prec.) 8
Previous work Previous work [BMT+21] N slot 214 23 23 23 212 Bit precision 15.5 45 100 100.11 93.03 Boot time 7.5s 32s 167s - - 215 216 217 217 217 [JM22] [LLK+22] There are various studies to obtain high precision Need large parameters such as ? = 217 Limit of maximum precision [BMT+21] Jean-Philippe Bossuat et.al. Efficient Bootstrapping for Approximate Homomorphic Encryption with Non-sparse Keys. Eurocrypt 2021 [JM22] Nathan Manohar Charanjit S. Jutla. Sine Series Approximation of the Mod Function for Bootstrapping of Approximate HE. Eurocrypt 2022 [LLK+22] Joon-Woo Lee et.al. High-Precision Bootstrapping for Approximate Homomorphic Encryption by Error Variance Minimization. Eurocrypt 2022 9
META-BTS BTS (low prec.) BTS (high prec.) Use a low-precision BTS as a building block for a high precision BTS Since we repeat low-precision BTS, modulus consumption of BTS is still low and we have more levels than just raising precision for each components of BTS 10
META-BTS - case k=2 1 2? ?1 ?0 ?1 ?0 ? 1. BTS input range limit BTS 2. ?1 ?1 ?0 ?1 ?1 ?0 2? ?1 ?1 ?1 ?1 ? 3. ?????1 ?1 ? ?1 ?1 ? 4. BTS 5. ?1 ?2 ?1 ? ??????5 ?1 ?1 ? ?1 ?0 ?2 6. 11
META-BTS n-bit BTS k-times ?? ?1 ?0 ? ?1 ?0 ?? ?? Given n-bit precision BTS, one can obtain a kn-bit BTS by repeating the bootstrapping algorithm k-times 12
Comparison Algorithm [BMT+21] N slot 214 23 23 23 212 214 215 216 Iter - - - - - 3 17 14 Bit precision 15.5 45 100 100.11 93.03 48 255 420 Boot time 7.5s 32s 167s - - 20s 300s 903s 215 216 217 217 217 215 216 217 [JM22] [LLK+22] This work Algorithm [LLK+22] This work N slot 216 216 Bit precision < 93 96 depth 3 9 time 101.5s 175.8s time/depth 33.8s 19.5s 217 217 13
META-BTS Provides higher precision BTS under the same parameters Improves asymptotic time complexity in BTS More levels for multiplication left after BTS Can use any BTS algorithm 14
The end 15
