Analysis, Design and Implementation of Advanced Optimization Strategies for the Marble FHE Compiler

Abstract

Collecting data and tracking users is a ubiquitous phenomenon in today’s data-driven world. Personalized services benefit from this data and offer useful services to their users. Ongoing data breaches have raised awareness for privacy among users, leading to a growing demand for solutions that ensure privacy while allowing users to benefit from personalized services. Motivated by that, governments have intensified their privacy efforts by imposing stricter laws on organizations, e.g., the General Data Protection Regulation (GDPR). However, regulatory measures alone are not sufficient to protect sensitive data against data misuse or data breaches. Concepts of advanced cryptography such as Fully Homomorphic Encryption (FHE) allow to both protect the privacy and preserve the utility of data. FHE allows privacy-preserving, outsourced computations on encrypted data. As such, it can enable businesses to provide personalized services while ensuring that individuals’ privacy is protected. Recent advancements in FHE already show practical performance for various real-world applications. However, a significant obstacle to the wider adoption of FHE is its low usability. Developing an FHE-based application that is efficient, and at the same time secure, currently remains a difficult task requiring significant cryptographic expertise and experience. Our approach is inspired by a lack of tools that allow non-expert developers to effortlessly transform traditional programs into ones that exploit the peculiarities of FHE. This gap in the current state of the art is highlighted by our extensive comparative study providing a systematical overview and analysis of a wide range of FHE optimizations. In this thesis, we present a collection of novel, fully automated, and transparent optimization techniques for FHE compilers that transform naively implemented programs, written by non-experts, into highly efficient programs that make use of established concepts employed by experts to manually push FHE’s performance to the limit. Our approach is based on batching computations that makes use of FHE schemes’ support for Single Instruction, Multiple Data (SIMD)-like operations. The evaluation of our automated optimization shows a run time speedup of more than 90x for a program performing Laplacian sharpening on a 64 × 64 px image. In addition, we present an algorithm to detect batchable expression subtrees in an Abstract Syntax Tree (AST) that might be of independent interest. Finally, we implement a variety of other optimization techniques that transform the AST to facilitate the detection of batching opportunities.