Theses

Error-Latency-Aware Scale Management Compiler for Fully Homomorphic Encryption [abstract] (PDF)
Yongwoo Lee
Ph.D. Thesis, School of Electronical and Electronic Engineering, Yonsei University, August 2024.

Owing to its capabilities for fixed-point arithmetic and SIMD-like vectorization, among fully homomorphic encryption (FHE) schemes that enable computations on encrypted data, RNS-CKKS stands out as a popular choice for privacy-preserving machine learning services. While previous efforts automate scale management essential for RNS-CKKS's fixed-point arithmetic, they show limited performance improvement and accuracy gain. This limitation restricts the ability of users to investigate and optimize the trade-off between error margins and latency.

This dissertation encompasses three pivotal studies that collectively advance the domain of fully homomorphic encryption (FHE), particularly the RNS-CKKS scheme, to bolster privacy-preserving machine learning services. The first study introduces HECATE, an innovative FHE compiler framework that optimizes ciphertext scales by leveraging a novel type system and a rescaling operation termed "downscale". HECATE analyzes various scale management plans for their expected performance impact, enabling optimal rescaling points throughout FHE applications.

The second study delves into the ELASM scheme, which proposes an error- and latency-aware scale management for RNS-CKKS, addressing the limitations of previous works that overlook the output error's impact. By actively managing the ciphertext scale, ELASM minimizes the error-latency cost function, introducing a new scale-to-noise ratio (SNR) parameter and noise-aware waterlines for enhanced error-latency trade-offs. This approach demonstrates superior performance on machine and deep learning benchmarks compared to existing solutions.

The third study proposes a performance-aware static scale analysis for RNS-CKKS programs, aimed at overcoming the challenges of manual scale management and the inefficiencies of existing compilers. Through backward analysis of the scale "reserve" of each ciphertext and a novel type system, this method redistributes scale budgets for performance-aware management.

Together, these studies present a comprehensive approach to optimizing FHE applications through advanced compiler frameworks, scale management schemes, and performance analysis techniques. They not only demonstrate the feasibility of efficient, privacy-preserving applications but also open new avenues for further research in optimizing encrypted computation, resulting in a 41.8% performance improvement over conservative static analysis approaches and significantly faster scale management times compared to exploration-based methods.