HECO: Automatic Code Optimizations for Efficient Fully Homomorphic Encryption

Published in arXiv preprint, 2022

Recommended citation: Alexander Viand, Patrick Jattke, Miro Haller, Anwar Hithnawi. (2022). "HECO: Automatic Code Optimizations for Efficient Fully Homomorphic Encryption" arXiv preprint, arXiv:2202.01649. https://arxiv.org/abs/2202.01649

Abstract

In recent years, Fully Homomorphic Encryption (FHE) has undergone several breakthroughs and advancements leading to a leap in performance. Today, performance is no longer a major barrier to adoption. Instead, it is the complexity of developing an efficient FHE application that currently limits deploying FHE in practice and at scale. Several FHE compilers have emerged recently to ease FHE development. However, none of these answer how to automatically transform imperative programs to secure and efficient FHE implementations. This is a fundamental issue that needs to be addressed before we can realistically expect broader use of FHE. Automating these transformations is challenging because the restrictive set of operations in FHE and their non-intuitive performance characteristics require programs to be drastically transformed to achieve efficiency. In addition, existing tools are monolithic and focus on individual optimizations. Therefore, they fail to fully address the needs of end-to-end FHE development. In this paper, we present HECO, a new end-to-end design for FHE compilers that takes high-level imperative programs and emits efficient and secure FHE implementations. In our design, we take a broader view of FHE development, extending the scope of optimizations beyond the cryptographic challenges existing tools focus on.

Full paper

My Contribution

I had the opportunity to contribute a Python frontend to HECO while working as a research assistant at the Privacy Preserving Systems (PPS) lab of ETH Zurich.

Other systems like Microsoft’s EVA trace computations and build a (potentially large) expression that represents the program’s computation. EVA then compiles this expression to SEAL code, which is a library for Fully Homomorphic Encryption (FHE). Unlike them, our frontend extracts the abstract syntax tree (AST) from the Python program and translates this to HECO’s internal AST. This internal AST still has standard programming paradigms such as loops. Later, HECO optimizes the internal AST and translates it to FHE code. Using an AST instead of a single expression to represent the user’s Python program enables high-level optimizations as it avoids obscuring the program structure.