Bootstrapping with CKKS: High-Precision Privacy-Preserving Computation
Explore the CKKS Homomorphic Encryption Scheme for precision computation and privacy-preserving machine learning. Learn about supporting high precision bootstrapping and increasing computational depth while maintaining security. Discover how error handling can lead to more efficient constructions in privacy-preserving computations.
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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Sine Series Approximation of the Mod Function for Bootstrapping of Approximate HE Charanjit S. Jutla and Nathan Manohar IBM T.J. Watson Research Center
CKKS HE Scheme (2017) Supports arithmetic circuits over the reals/complex numbers Only for approximate arithmetic Scheme Circuit Type Plaintext Type Mod ? BGV Arithmetic Mod ? BFV Arithmetic GSW Boolean Bits FHEW Boolean Bits TFHE Boolean Bits CKKS Arithmetic Real/Complex
CKKS HE Scheme (2017) Ideal for privacy-preserving machine learning Scheme Circuit Type Plaintext Type Mod ? BGV Arithmetic Mod ? BFV Arithmetic GSW Boolean Bits FHEW Boolean Bits TFHE Boolean Bits CKKS Arithmetic Real/Complex
CKKS HE Scheme (2017) Main insight: Treat error as part of approximate computation error Allows for much more efficient constructions! SK Dec: m m + error Lock - Free security icons
? Fresh Ciphertext 0 0 ? ? ? ? After 1 Multiplication 0 ? 0 ? ? After Several Multiplications 0 ? ? ?
Can we increase ? to support the depth of computation? Increasing ? decreases security! Need to increase ring dimension ? to compensate
? Fresh Ciphertext 0 0 ? ? ? Bootstrapping refreshes ciphertext After Several Multiplications 0 ? ? ?
This Work Can we support high precision bootstrapping?
This Work Can we support high precision bootstrapping? Yes, up to arbitrary precision! Our Implementation: 100 bits
Before Bootstrapping 0 ? ? ? ? After Modulus Raising ? 0 ? ? 0 ? ? After Bootstrapping 0 ? 0 0 ? ?
Bootstrapping for CKKS Coefficient rounding modulo ? Mod function not easily represented by a polynomial Operations on coefficients not slots Handled by applying homomorphic linear transforms Our focus
Approximating the Mod Function poly( ) ?? + ? ? Can assume ? << ? Mod Function Approximation Region Mod Function for ? = 1000
Main Challenges Approximation Error: Large error will destroy message precision ? After Modulus Raising ? 0 ? ? 0 ? ? After Bootstrapping 0 ? 0 0 ? ?
Main Challenges Approximation Error: Large error will destroy message precision ? After Modulus Raising ? 0 ? ? 0 ? ? After Bootstrapping 0 ? 0 0 ? ?
Main Challenges Polynomial Degree: Larger degree => larger multiplicative depth => more ciphertext modulus consumed to evaluate ? After Modulus Raising ? 0 ? ? 0 ? ? After Bootstrapping 0 ? 0 0 ? ?
Main Challenges Polynomial Degree: Larger degree => larger multiplicative depth => more ciphertext modulus consumed to evaluate ? After Modulus Raising ? 0 ? ? 0 ? ? After Bootstrapping ? 0 0 ? ?
Main Challenges Coefficient Magnitude: Larger coefficients => larger evaluation precision => more ciphertext modulus consumed to evaluate ? After Modulus Raising ? 0 ? ? 0 ? Small evaluation precision ? After Bootstrapping 0 ? 0 0 ? ?
Main Challenges Coefficient Magnitude: Larger coefficients => larger evaluation precision => more ciphertext modulus consumed to evaluate ? After Modulus Raising ? 0 ? ? 0 ? Large evaluation precision ? After Bootstrapping ? 0 0 ? ?
Approximating the Mod Function poly( ) ?? + ? ? Can assume ? << ? 1) Small Approximation Error 2) Low Degree 3) Small Coefficients
Prior Approaches to Mod Approximation Scaled sine approximation of mod function [CHK+18, CCS19, HHC19, HK20] Can only achieve low precision as sine approximation has fundamental cubic error. Other Approaches [JM20, LLL+21] [LLL+21] Algorithmic search on a composition of functions [JM20] Explicit formulas for direct polynomial approximation Coefficients of polynomials can be too large
Fourier Series Approximation Mod Function Approximation Region Fourier Series Fourier Series Approximation of Order 5
Fourier Series Approximation Approximation Region Sine Fourier Series Fourier Series Approximation of Order 5
Fourier Series Approximation Mod Function Approximation Region Sine Fourier Series Fourier Series Approximation and Sine Approximation 23
Fourier Series: The Bad Approximation Region Sine Fourier Series Fourier Series Approximation of Order 5 Performs poorly in approximation region!
Fourier Series: The Bad Approximation Region Sine Fourier Series Fourier Series Approximation of Order 5 Performs poorly in approximation region! Cannot be used for bootstrapping
Stepping Away From Fourier Series Suppose we want to approximate 2? Fourier series is linear combination of sin?,sin2?,sin3?, sin? sin2? sin3? 26
This Work Can we use a different linear combination to approximate the mod function?
This Work Can we use a different linear combination to approximate the mod function? Only focus on approximation region!
This Work: Sine Series Approximation Want to approximate 2?on inputs2?? + ?for small? sin ?(2?? + ?) = sin?? Enough to consider behavior for small ? ? Want ? ?=1 Easy to find such a linear combination Hard Part: Prove it gives exponentially good approximation ??sin(??) for small ?
Order 2 Approximation sin2? sin? 4 3sin? 1 6sin2? 30
Our Approximation Approximation Region Sine Mod Function for ? = 1000 with Scaled Sine Approximation 31
Our Approximation Approximation Region Sine Sine Series Sine Series Approximation of Order 2 32
Our Approximation Want to approximate 2?on inputs2?? + ?for small? Enough to consider behavior for small ? sin? = ? ?3 3!+?5 5! ?7 7!+ Error 33
Our Approximation sin? = ? ?3 3!+?5 5! ?7 7!+ sin2? = 2? (2?)3 +(2?)5 (2?)7 + 3! 5! 7! 34
Our Approximation 4 3sin? =4 3? 2 1 90?5 1 9?3+ 3780?7+ 1 6sin2? = 1 3? +2 2 45?5+ 4 9?3 945?7 35
Our Approximation 4 3sin? =4 3? 2 1 90?5 1 9?3+ 3780?7+ + 1 6sin2? = 1 3? +2 2 45?5+ 4 9?3 945?7 1 30?5+ 1 252?7 = ? Error 36
Our Approximation 4 3sin? =4 3? 2 1 90?5 1 9?3+ 3780?7+ + 1 6sin2? = 1 3? +2 2 45?5+ 4 9?3 945?7 1 30?5+ 1 252?7 = ? 37
Our Approximation 4 3sin? =4 3? 2 1 90?5 1 9?3+ 3780?7+ + 1 6sin2? = 1 3? +2 2 45?5+ 4 9?3 945?7 1 30?5+ 1 252?7 = ? 38
Our Approximation 4 3sin? 1 1 30?5+ 1 252?7 6sin2? = ? Can we cancel higher order terms? Yes! 39
Our Approximation Approximation Region Sine Sine Series Sine Series Approximation of Order 2
Our Approximation Approximation Region Sine Sine Series Sine Series Approximation of Order 3
Our Approximation Approximation Region Sine Sine Series Sine Series Approximation of Order 4
Our Approximation Mod Function Approximation Region Sine Series Sine Series Approximation of Order 4
Proof Challenges Taylor series error bound is not good! Need more advanced proof techniques Calculate determinants of generalized Vandermonde matrices Use well-known generating series of the complete homogeneous symmetric polynomials
Our Approximation Error of approximation is ?(??2?+1) where ? =? ? Mod Function Approximation Region Sine Series Sine Series Approximation of Order 4
Our Approximation Error of approximation is ?(??2?+1) where ? =? ? Mod Function Approximation Region Sine Series Sine Series Approximation of Order 4
Our Approximation Error of approximation is ?(??2?+1) where ? =? ? Sine was ?(??3) Mod Function Approximation Region Sine Series Sine Series Approximation of Order 4
Our Approximation We also show |?1| < 2 and |??| < 1 with ?? s alternating sign Error of approximation is ?(??2?+1) where ? =? ? Sine was ?(??3) Mod Function Approximation Region Sine Series Sine Series Approximation of Order 4
Our Approximation We also show |?1| < 2 and |??| < 1 with ?? s alternating sign Error of approximation is ?(??2?+1) where ? =? ? Small Coefficients Sine was ?(??3) Mod Function Approximation Region Sine Series Sine Series Approximation of Order 4
Homomorphically Computing Sine Series Can use Taylor series approximation of ??? to determine sin? ???= cos? + ?sin? Can compute ?2?? from ??? ?2??= cos2? + ?sin2?
