Fully Homomorphic Encryption (FHE) is a cryptographic technique that allows computations to be performed on encrypted data without having to decrypt it. This property preserves data privacy, enabling a wide range of applications in fields such as cloud computing, secure data analysis, and privacy-preserving machine learning.

In FHE computations, each ciphertext can only handle a limited number of operations before the accumulation of noise makes decryption impossible. To resolve this, the bootstrapping operation must be used to reset the noise in the ciphertext. Bootstrapping is a computationally expensive computation, and it also influences the costs of other operations. Consequently, the strategic placement of bootstrapping operations is a critical aspect of FHE performance.

This thesis introduces Saturn, a novel method for automatically determining the optimal placement of bootstrapping operations to minimize program runtime. Given a directed acyclic graph (DAG) representing an FHE computation, Saturn leverages the Maximum Satisfiability (MaxSAT) optimization problem to find the most effi- cient bootstrapping placement. A key innovation in Saturn is the introduction of two methods for reducing the complexity of the input computational DAG: Quadratic Behavior Profile (QBP) Reduction and Auto-Compression. These methods signifi- cantly decrease the solve time of our MaxSAT formulation by simplifying the DAG while preserving the optimality of the solution. Saturn's effectiveness is evaluated on various deep learning models, demonstrating its potential to enhance FHE performance through efficient bootstrapping placement.

62 pages

Thesis Committee:
Wenting Zheng (Chair)
Fraser Brown

Srinivasan Seshan, Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu