UCLA

The CKKS homomorphic encryption scheme is a homomorphic encryption scheme that supports approximate arithmetic over real/complex numbers. Due to its ability to natively compute over real numbers, the CKKS homomorphic encryption scheme is considerably more efficient than other schemes for many real world applications that naturally lend themselves to computation over real numbers. Such applications include, for example, privacy-preserving machine learning and secure genome analysis.

In the CKKS homomorphic encryption scheme, ciphertexts have an associated level, which is reduced as homomorphic computation is performed. Eventually, a ciphertext is at the lowest level, and no further homomorphic computation can be performed. In order to evaluate high depth circuits, it is necessary to bootstrap a ciphertext using a procedure called bootstrapping, which takes a ciphertext at the lowest level and increases its level so that additional homomorphic computation is possible. Unfortunately, the bootstrapping procedure for CKKS has a large associated error, and, prior to this work, it was not possible to perform high precision computations in CKKS since bootstrapping would reduce the precision of the plaintext. Obtaining high precision bootstrapping of CKKS is particularly important since many applications of CKKS require high precision computation.

In this dissertation, we show how to obtain high precision bootstrapping of CKKS. The main challenge is to find low-degree polynomial approximations of the mod function in small intervals around multiples of the modulus. We show the above by first showing how to approximate the mod function in epsilon-sized intervals around multiples of the modulus using a sine series, where our sine series of order n has error O(epsilon^{2n+1}). This, after a Taylor series approximation of the sine function, results in a low-degree polynomial approximation of the mod function with small coefficients that can be used to approximate the mod function to arbitrary precision, resulting in practical high precision bootstrapping of the CKKS homomorphic encryption scheme. We validate our approachby an implementation and obtain 100 bit precision bootstrapping as well as improvements over prior work even at lower precision.

The contents of this dissertation are based on a joint work with Charanjit S. Jutla.