# HECO: Automatic Code Optimizations for Efficient
Fully Homomorphic Encryption

Alexander Viand, Patrick Jattke, Miro Haller, Anwar Hithnawi

ETH Zürich

###### 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.

##  1 Introduction

Privacy and security are gaining tremendous importance across all
organizations, as public perception of these issues has shifted and
expectations, including regulatory demands, have increased. This has led to a
surge in demand for secure and confidential computing solutions that protect
data confidentiality while in transit, rest, and in-use. Fully Homomorphic
Encryption (FHE) is a key secure computation technology that enables systems
to preserve the confidentiality of data end-to-end, including while in use.
Hence, allowing outsourcing of computations without having to grant access to
the data. In the last decade, advances in FHE schemes have propelled FHE from
a primarily theoretical breakthrough to a practical solution for a wide range
of applications [1, 2, 3]. In recent years, we have seen FHE emerging in real-
world applications, e.g., Microsoft’s Edge browser uses FHE to realize its
privacy-preserving password monitor [1]. With upcoming dedicated hardware
accelerators for FHE promising further speedup [4, 5], FHE will soon be
competitive for an even wider set of applications. Today, FHE is promising to
become a major driver in transforming privacy. For example, a recent report by
Gartner, Inc. predicts [6, 7] that FHE “will be a core technology for many
future SaaS offerings.”

Though promising in its potential, developing FHE applications, unfortunately,
remains a complex and tedious process. Writing efficient FHE programs that
deliver on their potential performance is currently a complicated and tedious
task that even experts struggle with. FHE’s use in practice and at scale is
today primarily hindered by its complexity rather than its performance. These
complexities derive from the need to map applications to the unique
programming paradigm imposed by FHE (c.f. § 2.3). Code that is properly
optimized for this paradigm is often overwhelmingly more efficient than poorly
adapted code, with speedups of several orders of magnitude being common.
Therefore, optimizing applications and rewriting them to match FHE’s
programming paradigm is essential for practical applications of FHE. Today,
this remains an unresolved issue posing a major barrier to wider adoption.

In order to facilitate easier development of FHE-based privacy preserving
technologies, the current FHE development ecosystem must better address the
needs of non-expert developers. Existing tools fail to provide an easy-to-use,
general-purpose, and flexible toolchain to transform high-level code written
by non-experts into efficient FHE implementations that match the performance
of those created by experts. Ideally, developers should not need to adapt to
FHE’s unique paradigm, making only minimal changes to their code such as
marking inputs as secret. Instead, tools should bridge the gap between
traditional programming patterns and the restrictions of FHE development by
automatically rewriting and optimizing programs to match FHE’s unique
programming paradigm. Existing domain-specific tools have partially addressed
this for some scenarios [8, 9, 10], but a lack of flexibility prevents their
use when developers’ needs are even slightly misaligned. General-purpose
tools, on the other hand, either sacrifice performance for ease-of-use [11,
12, 13] or require the developer to manually map their application to the FHE
paradigm [14, 15].

In order to overcome these limitations, we need to fundamentally _rethink the
architecture of FHE compilers_ and _develop novel optimizations_ that address
the limitations of existing tools. In this paper, we present HECO, a new FHE
compiler and propose a holistic architecture for FHE compilers that, for the
first time, provides a true end-to-end toolchain for FHE development. In
addition, we propose novel transformations and optimizations that map standard
imperative programs to the unique programming model of FHE.

#### E2E Architecture

Compilers need to to be able to accommodate a wide variety of optimizations
required to develop efficient FHE applications. We identify three distinct
phases that constitute the process of converting an application to an
efficient FHE implementation: _(i)_ Program Transformation, which restructures
a high-level program to become efficiently expressible using native FHE
operations, _(ii)_ Circuit Optimization, which primarily focuses on changes
that reduce noise growth in the FHE computation (which, at this point, is
equivalent to an arithmetic circuit), and _(iii)_ Cryptographic Optimization,
which instantiates the underlying scheme as efficiently as possible for the
given program. Based on these insights, we propose a set of Intermediate
Representations (IRs) that match the requirements of each phase, allowing us
to naturally and efficiently express optimizations for each phase.

Most existing tools focus on the second, and to some extent third, phase of
this process. This is reflected in their design, using internal representation
that map directly to native FHE operations. Therefore, they are limited to
optimizations expressible at this level and cannot easily be extended to
address the first phase of FHE development. In HECO, we extend compilation to
support all phases and introduce novel optimizations targeting the first phase
of development.

#### Automated Mapping to Efficient FHE

We expand the FHE compilation chain with support for the automatic
transformation of high-level programs to FHE’s unique programming paradigm.
Experts spend significant time considering _how_ to best express an
application in the FHE paradigm, only considering the other aspects once the
program is _efficiently_ expressible using native FHE operations. Existing
tools, in contrast, nearly universally disregard this arguably most important
phase of the FHE development process.

In HECO, developers are able to express their algorithms conveniently in the
standard imperative paradigm, making use of, e.g., loops that access and
manipulate vector elements by accessing individual elements. However, such
programs do not align well with the restricted set of operations offered by
FHE schemes, requiring the compiler to translate and restructure the
application. We specifically focus on transformations targeting the Single
Instruction, Multiple Data (SIMD) parallelism present in most modern schemes,
which allows one to _batch_ many (usually $2^{13}-2^{16}$) different values
into a single ciphertext and compute over all elements simultaneously.
Batching is used by experts to drastically reduce ciphertext expansion and
computational overhead, frequently improving runtimes by several orders of
magnitude when compared to naive implementations.

While it is arguably the single most important optimization for many
applications, unlocking the performance potential of batching is currently
restricted to experts with significant expertise and experience in writing FHE
applications. Existing algorithms must be translated to ones expressed solely
as SIMD operations and _rotations_ , as the only natively supported data
movements in FHE are cyclical rotations of the elements inside a ciphertext.

HECO converts operations over vector elements into efficient SIMD operations
in this paradigm. Emulating element-wise operations is highly inefficient in
batched FHE, requiring expensive FHE operations. Instead, HECO employs a
series of transformations and optimizations that aim to remove the need to
operate over individual vector elements. We replace individual element-wise
operations with SIMD operations, which requires introducing additional
operations to maintain the consistency of the program. However, our
transformations are carefully designed to allow us to optimize the resulting
program further, eliminating the vast majority of introduced operations. In
our evaluation, we show that HECO can match the performance of expert
implementations, providing up to 3500x speedup over naive non-batched
implementations.

Beyond the contributions we present in this paper, we make our system
available as an open-source project and we hope that HECO will help to advance
the FHE development ecosystem. HECO decouples optimizations from front-end and
back-end logic, allowing it to easily be extended for different languages, FHE
libraries or accelerators, and novel optimizations as they emerge. We build
HECO on top of the open-source MLIR framework [16], which is rapidly
establishing itself as the go-to tool for domain-specific compilers and opens
up the possibility of exchanges of ideas and optimizations even beyond the FHE
community.

##  2 Background

Figure 1:  In FHE, a third-party can compute on encrypted values without
requiring access to the underlying data.

In this section, we briefly introduce the notion of Fully Homomorphic
Encryption (FHE) and key aspects of modern FHE schemes.

###  2.1 Fully Homomorphic Encryption

In a _homomorphic_ encryption (HE) scheme there exists a homomorphism between
operations on the plaintext and operations on the ciphertext, so that

$\operatorname{Dec}(\operatorname{Enc}(x+y))=\operatorname{Dec}(\operatorname{Enc}(x)\oplus\operatorname{Enc}(y)).$

This allows a third-party to compute on encrypted data without requiring
access to the underlying data. For example, a client can privately outsource
computation by encrypting the data before sending it to the cloud, where the
function is computed over ciphertexts, as shown in Figure 1. The client can
decrypt the returned result, while the server learns nothing about inputs,
intermediate values or results. In addition to outsourcing a computation, HE
can also be used for two-party computations, where the server provides either
some of the inputs, the function, or both. For example, in Microsoft Edge’s
password monitor [1], the client sends encryptions of stored logins to the
server which compares them against its list of known leaked usernames and
passwords.

While _additively_ or _multiplicative_ homomorphic encryption schemes such as
the Paillier encryption scheme [17] or textbook RSA [18] have been known for
many decades, _fully_ homomorphic encryption (FHE) schemes that support an
arbitrary combination of both operations remained unrealized until 2009 when
Craig Gentry presented the first feasible FHE scheme [19]. Since then, the
performance of these schemes has continued to improve dramatically: While the
initial FHE schemes took around half an hour to compute a single
multiplication, modern schemes require only a few milliseconds. Nevertheless,
this still represents a slowdown of seven orders of magnitude compared to a
standard imul executed on a modern CPU. With the emergence of dedicated FHE
hardware accelerators, this gap will be reduced by several orders of
magnitude.

###  2.2 FHE Schemes

We briefly describe the BFV scheme [20, 21], focusing on aspects relevant to
FHE application development and referring to the original papers for further
details. Since most modern FHE schemes follow a similar pattern, the
descriptions also mostly apply to the BGV and CKKS schemes [22, 23].

In BFV, plaintexts are polynomials of degree $n$ (usually $n>2^{12}$) with
coefficients modulo $q$ (usually $q>2^{60}$). Encryption introduces a small
amount of _noise_ into the ciphertext. This is initially small enough to be
rounded away during decryption, but grows during homomorphic operations. If
left unmanaged, the noise will eventually corrupt the ciphertext, leading to
failed decryptions.

BFV supports additions and multiplications over ciphertexts, with additions
increasing noise only negligibly, while multiplications significantly increase
the noise.

This limits computations to a (parameter-dependent) number of consecutive
multiplications (multiplicative _depth_) before decryption fails. Using the
Chinese Remainder Theorem (CRT), it is possible to _encode_ a vector of $n$
integers into a single polynomial, with addition and multiplication acting
slot-wise (SIMD). Since the polynomial degree $n$ is usually $2^{13}-2^{16}$
in order to ensure security, this can significantly reduce ciphertext
expansion and computation cost. This creates a significant opportunity for
optimizing programs to fully exploit these large vectors. BFV also supports
rotation operations over such _batched_ ciphertexts, which rotate the elements
inside the vector cyclically. Finally, BFV includes a variety of noise-
management (or _ciphertext maintenance_) operations which do not change the
encrypted message but can reduce noise growth during computations.

###  2.3 FHE Programming Paradigm

We analyze and discuss the programming challenges FHE imposes, highlighting
their impact on the development process. Some of the challenges derive
directly from the definition of FHE and its security guarantees, while others
result from the restrictions and cost models of the schemes. Both developers
and FHE tools need to map applications to the unique programming paradigm of
FHE in order to achieve practical and efficient FHE solutions.

Figure 2:  Overview of HECO’s end-to-end approach.

#### Restricted Set of Operations

FHE schemes offer a very limited selection of data types and operations, with
additions and multiplications as the basic operations of FHE. FHE over binary
plaintext spaces ($\mathbb{Z}_{2}$) can emulate arbitrary computation.
However, the best performance is usually achieved when using non-binary
plaintext spaces (e.g., $\mathbb{Z}_{t}$ for $t\gg 2$). In this setting,
computations are equivalent to arithmetic circuits, which can only compute
polynomial functions. While it is possible to approximate many functions using
polynomials, this is frequently prohibitively inefficient in the context of
FHE. Instead, developers need to rethink their approach, e.g., using different
algorithms that are purely polynomial or well-suited to low-degree polynomial
approximations.

More fundamentally, FHE does not support branching based on secret inputs, as
revealing even the single bit required to branch would violate the security
properties of FHE. While it possible to _emulate_ some forms of branching,
this requires evaluating both sides of each branch. As a result, it is
inefficient and results in programs that perform worse than the worst-case
performance of the original program, even before considering FHE overhead.

While the requirement for branch-free programs is inherent in the definition
of FHE, future schemes might eventually remove the need to choose between
inefficient binary emulation of arbitrary functions or efficient integer-based
evaluation of polynomials. Recent works have explored homomorphic conversions
between different schemes [24, 25] or introduced the notion of _programmable
bootstrapping_ to approximate non-polynomial functions [26]. However, both
approaches are not yet practical enough for widespread adoption.

####  SIMD Parallelism

Since FHE ciphertexts in most modern FHE schemes must be very large for
security reasons, using them to encrypt, e.g., a single integer is inherently
inefficient. However, these schemes support _batching_ , which allows one to
encrypt many messages into the same ciphertext, reducing ciphertext expansion.
In this setting, FHE operations act in a Single Instruction, Multiple Data
(SIMD) fashion, i.e., element-wise. Since operating over batched ciphertexts
has the same cost as operating over individual values, batching is a key
component of designing efficient FHE solutions.

While it is trivial to use SIMD batching to increase throughput by processing
many inputs at the same time, this is often not feasible in practice since
many applications either do not feature enough inputs to fill a large
ciphertext vector or are primarily latency limited. The challenge, therefore,
is to use batching to accelerate the computation on a single (or a small
number of) input(s). Once a ciphertext has been encrypted, we are limited to
cyclical rotations and element-wise SIMD operations acting over all slots,
since there are no native scatter/gather operations. The challenge of this
paradigm arises from the complexity of efficiently computing functions where
values from many different slots need to interact with each other.

We discuss these challenges in further detail in § 4, demonstrating how
expert-optimized batched solutions can be nearly unrecognizable
transformations of the original program.

###  2.4 Security

Modern FHE schemes rely on post-quantum hardness assumptions that are widely
believed to be secure for the foreseeable future. The community has developed
a relatively stable estimation of the concrete hardness of many of these
problems [27] and parameter choices for a number of FHE schemes have been
standardized [28]. Nevertheless, some attention must be paid to security when
using FHE.

Most importantly, it is worth noting that FHE does not provide _integrity_ by
default, i.e., a server might perform a different calculation than the client
requested or even no calculation at all. There exist techniques to address
integrity, this range from zero-knowledge-proofs to hardware attestation [29].
Additionally, FHE does not by default provide _circuit privacy_ , i.e., a
client might be able to learn information about the circuit the server
applied. Different techniques, varying in practicality and level of
protection, can be used to address this [30, 31]. Finally, there are some
subtle issues that can appear when using _approximate_ homomorphic encryption
(e.g., Cheon-Kim-Kim-Song (CKKS)). Since these arise only in the somewhat
unlikely case that a third party gains access to a large number of high-
precision ciphertext decryptions for which it exactly knows the computation
performed on the ciphertexts, we merely note their existence and refer to the
paper [32] for further details.

##  3 End-to-End FHE Compiler Design

This section provides a system overview of HECO and presents its core
components.

###  3.1 System Overview

In HECO, developers express their programs using high-level languages (Python
or a C-like domain-specific language), which are translated to a high-level
Intermediate Representation (IR) that retains information from the input
program beyond what is directly expressible in FHE. This representation is
then optimized and lowered through a series of passes and IRs, arriving at a
low-level program expressed in a cryptographic IR that corresponds directly to
native FHE operations. Code-generation then translates this to calls to the
underlying FHE implementation (e.g., Microsoft’s SEAL library). An overview of
this end-to-end approach can be seen in Figure 2.

In order to enable a more holistic view of FHE compilation than existing tools
offer, we design HECO to support a range of different Intermediate
Representations (IRs) that enable it to apply optimizations from all three
stages of FHE development: _(i)_ Program Transformation, which restructures a
high-level program to become efficiently expressible using native FHE
operations, _(ii)_ Circuit Optimization, which primarily focuses on changes
that reduce noise growth in the FHE computation (which, at this point, is
equivalent to an arithmetic circuit), and _(iii)_ Cryptographic Optimization,
which instantiate the underlying scheme as efficiently as possible for the
given program. HECO’s design allows it to implement optimziations that other
tools cannot express, and its modular nature allows optimizations across
different layers to co-exist. In the remainder of this section we describe
HECO’s components, abstractions, and optimizations.

###  3.2 Front End & High-Level IR

HECO allows developers to express their programs in the same imperative
paradigm they are used to, using high-level languages. In addition to a custom
C-like Domain-Specific Language (DSL), we provide a Python-based front-end
which allows developers to work with FHE in a familiar environment, using
Python type hints to annotate which inputs are secret. In order to avoid
improving ease-of-use at the cost of expressiveness, HECO also exposes
advanced features like rotations and ciphertext maintenance operations through
built-in functions that seamlessly integrate with the front-end language.

In order to acquire the desired high-level representation of the input
program, HECO’s front-end differs fundamentally from other FHE compilers.
Existing tools mostly rely on replacing secret variables with placeholder
objects that record operations performed on them during execution of the host
language program, which condenses an entire function into a single gigantic
expression. This obscures the program structure, preventing efficient high-
level program transformations. Therefore, HECO instead parses the input
program, using the placeholder-object approach only for calls to externally
defined functions. Each front-end maps the language-specific parsed Abstract
Syntax Tree (AST) to a common AST representation, allowing language-
independent aspects (e.g., translation to Static Single Asignment (SSA) form)
to be shared among all front-ends.

###  3.3 Transformation & Optimization

Figure 3:  Overview of HECO’s dialects, which define the operations used in
the Intermediate Representations (IRs).

During the core part of the compilation process, the program is progressively
_lowered_ to more concrete, lower-level representations until the high-level
input program has been converted into a program from which FHE application
code can be generated directly. These lowering do not need to apply to the
entire program at once, in fact, programs will commonly consist of a mix of
different levels of abstractions. This is realized using the MLIR compiler
framework [16] where operations from several _dialects_ representing different
levels of abstraction can co-exist in a single intermediate representation.
Figure 3 provides an overview over the various dialects used in HECO, showing
where they are employed and what types of operations they provide.

Existing FHE compilers frequently use circuit-like IRs, as FHE computations
are equivalent to arithmetic circuits. Some earlier work also chose circuit
IRs in the hope of applying existing techniques from the hardware domain.
However, this has not produced significant performance gains so far [33] and
it seems likely that high-impact FHE optimizations will continue to require
custom designs. Since HECO needs to process high-level input programs that are
not yet equivalent to circuits, we use Static Single Asignment (SSA) form
based IRs that can represent a wider set of operations than circuit-based IRs
modeling native FHE operations. This approach is also used for low-level FHE
scheme IRs, providing a consistent interface for optimizations across the
entire toolchain.

The transformations and optimizations in HECO are grouped according to the
three stages we identified, and we present them accordingly in the following.
However, the modular nature of the passes which implement the various
optimizations also allows advanced users to dynamically compose compilation
pipelines for specific scenarios. The modularity also facilitates simple
extensibility of the compiler as new optimization techniques are developed by
the FHE community.

#### Program Transformations

The first phase of HECO maps the input program from the traditional imperative
paradigm to FHE’s unique programming paradigm. Existing tools either require
developers to perform this mapping manually or rely on trivial transformations
that generate prohibitively inefficient code. Most of the focus in the
development of FHE compiler optimizations has so far been on second-phase
circuit optimization and noise management techniques. However, even state-of-
the-art circuit optimizations [34, 35] are likely to accelerate a program by
only around 2x in practice [33]. In contrast, performance differences between
the runtimes of well-mapped and naively-mapped implementations can easily
reach several orders of magnitude [33].

In this mapping process, effective employment of batching is one of the main
differentiators between expert-written efficient solutions and impractical
naive approaches. The vast majority of state-of-the art FHE results rely on
the support for SIMD operations present in the BFV/BGV/CKKS family of R-LWE
based schemes [20, 21, 22, 23] to turn otherwise infeasible programs into
efficient secure solutions. While batching can be used to trivially increase
throughput, most FHE applications are constrained by latency. However,
employing batching effectively to improve performance on a single input is
non-trivial due to the restrictions imposed by FHE’s unusual programming
paradigm.

A significant part of our focus in HECO is consequently on automated batching
optimizations which we present in more detail in § 4. Note that our focus on
batching does not preclude other optimizations. Due to FHE’s high per-
operation cost, even a single redundant multiplication can have measurable
performance impacts. As a result, state-of-the-art expert-written code
frequently contains a significant boiler-plate code handling edge-case
optimizations. We implement a wide variety of general (e.g., constant folding,
common sub-expression elimination) and FHE-specific optimizations that allow
developers to write code in a more natural fashion by removing the need for
menial hand-optimization.

#### Circuit Optimizations

In the second phase, the program is conceptually equivalent to an arithmetic
circuit of native FHE operations. Optimizations at this stage are mostly
concerned with noise management, which requires a scheme-specific approach.
Therefore, HECO includes scheme-specific IRs that model the native FHE
operations offered by the schemes and the appropriate ciphertext maintenance
operations. These IRs also model the variety of slightly specialized
operations that the underlying libraries might offer and which can be more
efficient than the generic version when applicable (e.g., squaring vs
multiplying). Existing work, much of which has focused almost exclusively on
this phase, has proposed a variety of techniques [36, 12, 14, 15, 35, 34], and
our system’s modularity allows HECO to be easily extended with further
optimizations as they emerge. We omit a detailed description of these
techniques here, as they are not the focus of this paper.

#### Cryptographic Optimizations

Finally, in the third phase there are _cryptographic optimizations_ focused on
instantiating the underlying FHE scheme as efficiently as possible. The
primary challenge is parameter selection, identifying the smallest (most
efficient) parameters where the noise capacity is sufficient to perform the
computation correctly. While different techniques have been proposed to
estimate the expected noise growth of an FHE program [37, 38], these tend to
significantly over-estimate noise growth [37], leading to unnecessarily large
parameter choices. As a result, experts primarily rely on a trial-and-error
process to experimentally determine the point at which noise invalidates the
results. HECO includes basic automatic parameter selection, but also allows
experts to easily override these suggestions.

With dedicated FHE hardware accelerators on the horizon [4, 5], there are
potential future optimizations at this level. While current software
implementations generally use FHE operations as the smallest unit of
abstraction, it is likely that FHE hardware will feature a lower-level
interface based on the underlying ring operations. This opens up further
optimization opportunities, e.g., by using intermediate results created during
one FHE operation in a following operation. HECO’s modular nature and ease of
extension via self-contained optimization passes should enable our system to
easily integrate such optimizations as they emerge.

[t]0.5

⬇

1Ctxt[N] foo(Ctxt[N] img) {

2 Ctxt[N] img2 = img;

3 int[3x3] w = {{1,1,1},{1,-8,1},{1,1,1}};

4 for x in 0..n:

5 for y in 0..n:

6 int t = 0;

7 for j in -1..2:

8 for i in -1..2:

9 t += w[i+1][j+1]*img[((x+i)*n+(y+j))%

10 img2[(x*n + y)%

11 return img2;

12}

Listing 1:  Textbook implementation of a simple sharpening filter

[t]0.45

⬇

1Ctxt foo_batched(Ctxt img) {

2 Ctxt r0 = img * -8;

3 Ctxt r1 = img << -n-1;

4 Ctxt r2 = img << -n;

5 Ctxt r3 = img << -n+1;

6 Ctxt r4 = img << -1;

7 Ctxt r5 = img << 1;

8 Ctxt r6 = img << n-1;

9 Ctxt r7 = img << n;

10 Ctxt r8 = img << n+1;

11 return 2*img-(r0+r1+r2+r3+r4+r5+r6+r7+r8);

12}

Listing 2:  Optimized batched solution of the same program Listing 3:  Both of
these functions apply a simple sharpening filter to an encrypted image of size
$n\times n=N$, by convolving a $3\times 3$ kernel ($-8$ in the center, $1$
everywhere else) with the image. The version on the left encrypts each pixel
individually, and follows the textbook version of the algorithm, operating
over a vector of $N$ ciphertexts. The version on the right batches all pixels
into a single ciphertext and uses rotations (<<) and SIMD operations to
compute the kernel over the entire image at the same time. Designing batched
implementations requires out-of-the-box thinking in addition to significant
expertise and experience.

###  3.4 Code Generation & Back-End

HECO supports two different back-end modes, one aimed at general use and an
‘expert’ mode designed for advanced users. In general use, the majority of
HECO is invisible to developers, who compile and run programs entirely from
the front-end language (e.g., Python). The front end integrates with the
compiler and the underlying FHE library to run the generated FHE application
and transparently route inputs and outputs. In the ‘expert’ mode, HECO instead
emits the C++ source code of the optimized FHE program designed to link
directly against the FHE library, allowing advanced users to analyze and
potentially modify the generated code. This addresses a limitation we observed
with existing tools, whose rigid nature frequently prevented experts from
taking advantage of them for more complex scenarios.

HECO is designed to rely on existing FHE implementations, such as those
provided by Microsoft’s Simple Encrypted Arithmetic Library (SEAL) [39]. While
there can be advantages to co-designing scheme implementations and compilers,
these do not outweigh the downsides of using custom scheme implementations.
Such an approach requires not only significant re-implementation, but also
effectively disconnects a tool from advancements in FHE research made in the
wider community. For example, Cingulata [12] uses a custom BFV implementation
that has been leapfrogged by BFV implementations in actively developed
libraries like SEAL. Translating our scheme-specific IRs to the function calls
of the various library APIs is mostly trivial, as there is a nearly 1:1
correspondence between the two. Beyond targeting libraries, HECO is also
designed to easily allow adding support for generating code targeting future
FHE-specific hardware accelerators [4].

##  4 Automatic SIMD Batching

HECO introduces new FHE-specific optimizations to automatically rewrite
standard imperative programs to match the unique programming paradigm of FHE,
harnessing the performance potential of the SIMD parallelism present in most
modern schemes by automatically identifying and exploiting opportunities to
apply batching. Due to the large capacity of FHE ciphertexts (usually
$2^{13}-2^{16}$ slots), effective use of batching is arguably the single most
important optimization for many applications, drastically reducing ciphertext
expansion overhead and computation time. However, unlocking the performance
potential of batching currently requires significant expertise and experience
in writing FHE applications: existing algorithms must be translated to ones
expressed solely as SIMD operations and rotations, as the only natively
supported data movements are cyclical rotations of the elements inside a
ciphertext.

Enabling _non-experts_ to write efficient and secure FHE applications requires
abstracting away the complexities of FHE development. In HECO, developers are
be able to express their algorithms conveniently in the standard imperative
paradigm, making use of, e.g., loops that access and manipulate vector
elements by accessing individual elements. However, such programs do not align
well with the restricted set of homomorphic SIMD operations and rotations
offered by FHE schemes, requiring the compiler to translate and restructure
the application. In the following, we describe the core idea behind our
automatic transformation, and then walk through the individual challenges and
our solutions on how to efficiently identify and exploit batching
opportunities.

###  4.1 Approach

There is a stark contrast between naively translated code and the expert-level
FHE-native code which HECO aims to produce. Rewriting code to operate
virtually exclusively on entire ciphertexts rather than individual elements,
all while considering the restricted ability for data movement in FHE, usually
requires making far-reaching changes across the entire program. In fact, it is
not unusual for expert-optimized versions of FHE applications to be nearly
unrecognizable when compared to a non-FHE or naive implementation of the same
function, as can be seen in 3.

While program synthesis can achieve such drastic transformations [40], these
approaches are not always practical, taking minutes to optimize even
comparatively simple applications. Instead, we want to avoid the excessive
performance penalty of synthesis and achieve similar results in (fractions of)
seconds through a combination of efficient local transformations. Note that
traditional SLP vectorization algorithms [41, 42], which try to group
operations into SIMD instructions, do not apply in our setting. This is
because they generally rely on the ability to efficiently scatter/gather
elements into and out of vectors, something that is only possible at great
cost in FHE.

Since we want to target a broad range of domains and applications, our
transformations must be domain-independent and apply generically to a range of
different applications. We want to target generic patterns that are
independent of the function being computed, and do not consider optimizations
that change the application, such as moving parts of the computation to the
client-side.

Based on these requirements, HECO focuses its batching optimizations on
operations featuring vector111Vectors, arrays and (indexed) lists are
interchangeable for our purposes. elements. These are a natural target, as
well-written code featuring vectors is likely to be highly batchable, even if
this not immediately recognizable. While theoretically possible, searching for
batching opportunities across scalar variables is not only computationally
intensive, but also likely to result in no (significant) improvement in
overall performance: reasonably written code usually does not contain enough
‘free’ scalar variables to make batching worthwhile given the lack of
efficient scatter/gather operations and the very large capacity ($\geq 4096$)
of FHE ciphertexts.

#### Strawman Approach

Note that encrypting the elements of a vector into a single ciphertext instead
of a vector of ciphertexts does not improve performance unless the algorithm
is also modified to take advantage of this. Naively emulating operations over
individual elements would instead introduce significant overhead: Since native
FHE operations act equally on all ciphertext slots and values must be aligned
in the same slots to interact, emulating, e.g., x[i] = x[i] + y[j] with native
FHE operations introduces several additional steps. First, $y$ must be rotated
so that $y[j]$ is moved from slot $j$ to slot $i$. Then, the addition
operation must be applied to a copy of $x$ to avoid overwriting the other
slots. Finally, the updated copy and the original ciphertext must be
multiplied with complementary binary masks, so that when they are added, only
slot $i$ is set to the updated value. Due to the high cost of rotations and
multiplications, applying this trivial batching approach would be
prohibitively inefficient.

#### HECO’s Approach

Instead of naively translating element-wise operations to the native FHE
operations, HECO applies a series of transformations and optimizations that
aim to remove the need to operate over individual vector elements. Here, we
see a benefit of our high-level IR, which can contain ‘virtual’ operations
such as extract/insert operations which do not map directly to native FHE
operations. At its core, our optimizations replace each operation over vector
elements with an equivalent SIMD operation acting on entire vectors, inserting
‘virtual’ operations as required to maintain the internal consistency of the
program. While this might appear equivalent to the strawman emulation
approach, our transformations are carefully designed to allow us to optimize
the resulting program further. As a result, we can frequently completely
eliminate all ‘virtual’ operations without ever having to materialize them to
native FHE operations. Our batching optimization consists of several passes
with distinct purposes, which we group into a pre-processing stage and a main
stage for easier presentation.

#### Notation & Conventions

In the following, we assume vectors are batched into ciphertext slots
continuously (i.e., a ciphertext encrypting x contains x[i] in slot $i$) and
scalars are stored in the first slot (index $0$) of a ciphertext. Note that,
for ease of presentation, we use high-level code (e.g., x[i] + y[i]) for
examples, instead of following the structure of the SSA IR (e.g.,
%0=extract(x,i); %1=extract(y,i); %2=add(%0, %1)). The differences between the
IRs and equivalent high-level code are not relevant to understand the ideas
presented, but the SSA form is essential in enabling efficient implementations
of transformations.

###  4.2 Preprocessing

Before applying our batching transformations, we preprocess the program with
transformations that, while not directly batching-related, enable the
efficient optimizations in the following steps. In addition to standard
simplifications and canonicalizing the IR (i.e., bringing operations into a
standardized ‘canonical’ form to reduce the complexity of the IR), we also
apply two more specialized transformations.

#### Vectorizing Plaintexts

FHE applications frequently include operations between secret values and
_plaintext_ values that are known to the party performing the computation. For
example, an ML prediction-as-a-service server where clients provide encrypted
inputs still has access to the model parameters in plaintext form. Ciphertext-
plaintext operations are significantly more efficient than ciphertext-
ciphertext operations, and HECO exploits them whenever possible. In addition,
the presence of plaintext values can also enable further batching
optimizations. Hand-optimized FHE applications sometimes use unconventional
data layouts in order to improve performance. For example, matrix-vector
products can be significantly accelerated when the matrix elements are grouped
by their (generalized) diagonals, rather than row- or column-wise.

While re-arranging the layout of encrypted data requires expensive rotations,
masking, and combining, plaintext values can be freely (re-)arranged, opening
up opportunities for optimization. HECO batches plaintext values appearing in
ciphertext-plaintext operations involving vectors into the required slots. For
example, for z[i]=x[i]+a and z[j]=x[j]+b where a and b are plaintext values,
we replace them with vector elements by batching them into a vector p so that
p[i]=a and p[j]=b. This allows later batching optimizations to combine both
operation into a single SIMD operation. While this might not catch all
optimization opportunities, it is frequently sufficient to match expert-
designed approaches such as the diagonalized matrix-vector product example
mentioned above.

#### Merging Arithmetic Operations

During the preprocessing stage, we combine chained applications of
(associative and commutative) binary operations into larger arithmetic
operations with multiple operands (e.g., merging x=a+b; y=x+c to y=a+b+c).
While not an optimization in itself, it frequently enables other
simplification as it removes chains of dependencies and replaces them with a
single operation. It is also extremely useful in the context of ’fold’-style
operations such as computing the sum of all elements in vector (e.g., for i in
0..10: sum = sum + x[i]). This common pattern can be optimized in non-trivial
ways when using batched FHE, and this pre-processing step is essential in
allowing later stages to efficiently optimize such applications. Note that, in
the next section, we will use binary operations as examples for easier
presentation, but the techniques described readily generalize to operations
with more operands.

###  4.3 SIMD-ification

The goal of the main stage of our batching transformation is to eliminate
operations on individual vector elements, replacing as much of the input
program as possible with SIMD operations over entire ciphertexts. Many
traditional vectorization techniques targeting CPU vector extensions actively
search for combinable operations. These approaches generally rely heavily on
the ability to (re)-arrange vectors freely, making them ill-suited for FHE’s
more restrictive programming paradigm. Instead, HECO translates individual
operations over vector elements into equivalent SIMD operations over entire
ciphertexts, inserting ‘virtual’ insert/extract operations to maintain the
consistency of the IR. While this does not directly reduce the amount of work
the program is doing, the way we perform this transformation is carefully
designed to allow any inherent parallelism present in the input program to
emerge in a way that the compiler can easily recognize and simplify.
Therefore, the translation pass is followed by a ‘clean-up’ pass that realizes
the opportunities exposed by the translation pass. Finally, any remaining
‘virtual’ operations are efficiently lowered to native FHE operations,
completing the transformation of the program.

Our batching optimization takes as input a program, expressed in our high-
level SSA-based IR, that has undergone preprocessing but still contains
operations over elements of (secret) vectors. During the optimization, vector
types tensor<secret<T>> are translated to batchedsecret<T>, a high-level
scheme-independent abstraction of batched ciphertexts. After this pass
completes, the program contains only SIMD operations over entire vectors,
which can be realized using native FHE operations.

#### Translation Approach

At its core, this pass is a linear walk over all (arithmetic) operations in
the program. For each operation, we (i) transform the operands into a form
suitable for a SIMD-operation, (ii) issue the actual SIMD operation and (iii)
ensure the result is still valid for use in situations where a scalar is
expected (including uses in later operations that have yet to be transformed).
Since our batching convention uses slot 0 to store scalar values, an obvious
approach would be to rotate each operand (e.g. x[i]) so that the element of
interest ends up in slot 0. Then, performing the SIMD operation over the
rotated operands produces the result in the same slot, trivially ensuring the
result is in ‘scalar’ form (i.e., value in slot 0). While this approach is
correct and easy to implement, it is not a suitable approach for an optimizing
compiler, as it does not set the program up for further simplification.
Considering a loop (e.g., for i in 0..10: z[i]=x[i]+y[i]), each iteration
would have to be translated to a unique operation with distinct operands which
are each rotated by different amounts. Therefore, there is no immediate way to
collapse these into a single SIMD operation as desired.

Therefore, HECO uses a different approach, instead performing the SIMD
operation ‘in place’, avoiding rotations of the operands where possible.
Afterwards, the result is rotated from its current position (e.g., slot $i$)
to slot 0, to ensure consistency. While this might initially seems equivalent
to the first approach, it has a massive impact on the applicability of follow-
up optimizations. First, this can save a rotation (e.g., for x[i]+y[i]), as we
need only one for the result rather than one per operand. Second, and much
more importantly, in scenarios like the loop example mentioned above, the
addition operations in each iteration are duplicates of each other as they all
feature the same (non-rotated) inputs. Therefore, common sub-expression
elimination (CSE) during the clean-up pass can trivially simplify these
operations into a single SIMD operation that provides the results for all
iterations. This still leaves the result rotations, which are unique per-
iteration, but, as we will see later, these also frequently become redundant.

#### Operand Mapping

Our approach introduces a complexity not present in the naive approach: When
translating a statement with elements from different positions in their
vectors (e.g., x[i]+y[j]), we must first bring the elements of interest into
alignment by issuing a rotation for one of the operands. Note that this is no
worse than the naive approach, which always requires two rotations. Again, our
approach enables further simplifications when considering such operations
appearing inside a loop. While each iteration requires a rotation for one of
the operands, these are also all easy-to-simplify duplicates of each other, as
long as the _relative offset_ between $i$ and $j$ is constant. In order to
ensure that such simplifications are possible, the choice of rotation must be
the same for all equivalent operations. By setting the target slot to be the
first operand’s index and rotating the other operand to match, in combination
with having canonicalized the IR during pre-processing, we can ensure this is
always the case.

As mentioned earlier, the rotations of the results can also frequently be
optimized away. Specifically, when the result of an operation is assigned back
into a vector (e.g.,  z[i]=x[i]+y[i]), the rotations to slot 0 and then back
to $i$ cancel out and can be removed. In order to ensure this also works in
less straight-forward cases (e.g., z[i]=x[j]+y[i]), HECO’s target slot
calculation recognizes when the immediate uses of an operation include an
insertion operation and gives preference to the insertion’s target slot.

#### Realizing Fold Patterns Efficiently

Applying our batching transformation to fold or accumulation patterns (e.g.,
for i in 0..10: sum = sum + x[i] creates a linear number of rotations for the
inputs and, if necessary, an output rotation. Realizing the many-operand
arithmetic operation (c.f. § 4.2) using FHE also requires a linear number of
(binary) native FHE operations. While this might seem reasonable or even
optimal, we can significantly improve upon this when using batched FHE:
experts translate these fold patterns into _logarithmic_ series of rotations
and arithmetic operations by taking a copy of the current ciphertext, rotating
it by half the current work-set size (half/quarter/etc) and adding that
rotated ciphertext to the current ciphertext. The result then becomes the
current ciphertext and the process continues until, after only $\log n$ steps,
each slot contains the sum of all elements, as shown in Figure 4.

Figure 4:  Illustration of how repeated copying and rotating can be used to
compute the sum of all elements in a ciphertext in a logarithmic, rather than
linear, number of steps.

Clearly, this optimization requires a holistic view of the operation, which is
one of the reasons we merge operations during preprocessing. Given this
expanded representation of an operation, we can efficiently determine if it is
a candidate for a fold-style transformation. While we used a sum over all
elements as an example here, the technique can be generalized to any subset
with a consistent stride. When applied to multiplication, it additionally has
the benefit of automatically reducing the multiplicative depth of the
expression as a side-effect.

Note that the pre-processing combination of binary operations into larger
operations _must_ happen before the batching translations described above, as
the batching pass would otherwise insert rotations between the different
operations, making them no longer directly chained. The actual translation to
a series of rotations and native binary operations, meanwhile, has to be
performed after the batching transformation described above, since it requires
the operands to be entire ciphertexts, rather than scalars. Additionally, the
de-duplication simplifications that can take place after the batching
transformation can widen the applicability of this transformation by reducing
the number of distinct ciphertexts appearing in the program. This is an
example of emergent optimizations that occur not due to any individual
transformation, but from the combination of many different transformations and
simplifications adding up to more than the sum of its parts.

After these passes, and the associated clean-up passes, the program has been
transformed, as far as possible, into an optimized and efficient batched
program. Any operations (e.g., rotations) we introduced for consistency that
have not been simplified away, are likely to be fundamental components of the
algorithm. In the ideal case, the program is now equivalent to what an expert
developer would have written.

##  5 Implementation

We build HECO on top of the open-source MLIR framework [16], which is rapidly
establishing itself as the go-to tool for domain-specific compilers and opens
up the possibility of exchanges of ideas and optimizations even beyond the FHE
community. HECO consists of roughly 15k LOC of C++, with around 2k LOC of
Python for the python front-end. HECO uses the Microsoft Simple Encrypted
Arithmetic Library (SEAL) as its FHE backend. SEAL, first released in 2015, is
an open-source FHE library implemented in C++ that is thread-safe and heavily
multi-threaded itself. SEAL implements the BFV and CKKS schemes, and a fork
implementing the BGV scheme is available, too.

In contrast to existing, monolithic, compilers, HECO is highly modular and
designed to be flexible and extensible. We decouple optimizations from front-
end logic, allowing for a wide variety of domain-specific front-ends and the
ability to easily replace back-ends to target different FHE libraries or
hardware accelerators as they become available. The toolchain can easily be
adapted to different needs, with certain optimizations enabled or disabled as
required.

##  6 Evaluation

HECO is designed to compile high-level programs, written by non-experts in the
standard imperative paradigm, into highly efficient batched FHE
implementations that achieve the same performance as hand-crafted
implementations by experts. HECO achieves its usability goals through a well-
integrated Python front-end and by requiring developers to alter their code
only minimally (annotating variables as secret). However, ease-of-use becomes
moot when the performance of the generated code is not competitive. Therefore,
we focus our evaluation on the performance of HECO and the code it generates,
trying to answer whether or not automatic optimizations can bring naive code
to the same performance level as expert implementations.

Figure 5: Runtime of example applications (in seconds), comparing a naive non-
batched baseline, the solution generated by our system (HECO), and an
optimally-batched solution synthesized by the Porcupine tool.

###  6.1 Evaluation Setup

We compare the solutions generated by HECO to a naive non-batched baseline and
an optimally-batched synthesized solution. We report the run-time of the
computation and the speedups achieved. We also present some insights into
memory usage, which can be a limiting factor for non-batched approaches. In
addition to metrics about the generated programs, we report on the compile-
time of HECO. Especially for non-experts, a fast development cycle that allows
iterating on ideas and development in ‘real time’ has a significant effect on
user experience.

#### Baseline

Our baseline is a naive implementation of the application without taking
advantage of batching, as one might expect FHE novices to implement. In this
setting, vectors of secrets are directly translated to vectors of ciphertexts.
Since the underlying FHE libraries usually provide rather low-level APIs, even
this ‘naive’ baseline is not trivial to implement. While this approach
introduces significant ciphertext expansion and increases the memory required,
it is actually preferable in terms of run-time over a solution that batches
vector data into ciphertexts, but does not re-structure the program to be
batching-friendly. This is because such a solution adds the overhead of
rotations, masking, etc., to the base runtime of the non-batched solution.

#### Synthesis

Synthesis based approaches explore the space of all possible programs,
constrained by a reference specification describing input-output behavior.
While this tends to be computationally expensive, it has the potential to find
optimal solutions featuring highly non-intuitive optimizations. Porcupine [40]
is a synthesis-based compiler for batched FHE, using synthesis to find an
optimal batching pattern for a given application. In addition to a reference
specification, it takes a developer-provided sketch of an initial possible
batched approach. In some cases, their synthesized solutions outperform even
the previously accepted state-of-the-art approaches used by experts. While the
significant search time Porcupine requires to find these solutions (over 10
minutes to synthesis a program with 10 instructions) makes it less practical
for day-to-day development, it provides a useful lower bound to compare our
optimizations against.

#### Environment

All benchmarks are executed on AWS m5n.xlarge instances which provide 4 cores
and 16 GB of RAM. We used Microsoft SEAL [39] as the underlying FHE library,
targeting its BFV [20, 21] scheme implementation. All experiments are run
using the same parameters which ensure at least 128-bit security. We only
report the runtime of the computation itself, omitting client-side aspects
such as key-generation or encryption/decryption. All results are the average
of 10 iterations, discarding top and bottom outliers.

(a) Roberts Cross benchmark runtime (in seconds).

(b) Hamming Distance benchmark runtime (in seconds).

(c) Roberts Cross benchmark memory usage (in MB).

(d) Hamming Distance benchmark memory usage (in MB).

Figure 6: Log-log plot of the runtime and memory consumption of the roberts
cross and hamming distance benchmarks for different vector sizes, comparing a
naive non-batched solution with the batched solution generated by our system.

#### Applications

We compare the baseline, HECO and synthesis approaches on a set of nine
benchmark applications that represent a variety of common code patterns
relevant to batching. These programs range from having no inter-element
dependencies (e.g., Linear Polynomial), to simple accumulator patterns (e.g.,
Hamming Distance) and complex dependencies across a multitude of different
vector elements (e.g., Roberts Cross). As a result, they provide a useful
benchmark especially for batching optimizations.

These benchmarks were first proposed by Porcupine, and our ‘synthesis’
solutions are based on pseudo-code made available in an extended version of
the paper [40]. The synthesized dot-product code targets 8-element vectors,
while those for Hamming Distance and L2 Distance were provided for 4-element
vectors. For the other applications, we use vectors of length 4096,
representing 64x64 pixel images.

In the following, we briefly describe two applications which we will explore
in more detail, as they are representative of common batching opportunities.
The _roberts cross operator_ is an edge-detection feature used in image
processing. It approximates the gradient of an image as the square root of the
sum-of-squares of two different convolutions of the image, which compute the
differences between diagonally adjacent pixels. As in all other kernel-based
benchmarks, wrap-around padding is used, which aligns well with the cyclical
rotation paradigm of FHE. In order to enable a practical FHE evaluation, the
final square root is omitted, since it would be prohibitively expensive to
evaluate under encryption. The _hamming distance_ , meanwhile, computes the
edit distance between two vectors, i.e., the number of positions at which they
disagree. Here, we consider two binary vectors of the same length, a setting
in which computing (non-)equality can be done efficiently using the arithmetic
operations available in FHE. Specifically, this makes use of the fact that
$\mathrm{NEQ}(a,b)=\mathrm{XOR}(a,b)=(a-b)^{2}$ for $a,b\in\\{0,1\\}$.

###  6.2 HECO’s Performance

We start by comparing the performance of HECO’s generated solutions against
the baseline and synthesis approaches. Since the synthesis approach does not
scale to larger settings, we then dive into a more detailed evaluation of how
HECO performs across different sizes of inputs, comparing HECO against the
baseline in run-time and memory consumption, and also provide insights into
compile times.

As we can see from Figure 5, HECO dramatically improves performance over the
non-batched baseline approach. For example, for the Roberts Cross benchmark,
our batched solution is over 3500 times faster than the non-batched solution,
taking less than 0.04 seconds instead of over 2.35 minutes. In addition, our
results are nearly equivalent to the optimally batched solutions synthesized
by Porcupine, especially when considering the stark contrast between the non-
batched and the two batched solutions. In some cases (e.g., Box Blur),
Porcupine has an advantage because it finds non-intuitive solutions beyond
traditional batching patterns. Interestingly, for some applications (e.g.
Hamming Distance) HECO actually outperforms Porcupine. This is because
porcupine provides an optimally batched solution, but does not necessarily
handle ciphertext management optimally, inserting unnecessary relinearization
operations.

In order to better demonstrate the effect of batching on application
performance, we explore two of the benchmark applications in further detail,
exploring how runtime, speed-up, memory usage, and compile time vary with the
size of the input program.

#### Roberts Cross Operator

In Figure 6(a)/6(c), we show the runtime and memory requirements of the
Roberts Cross benchmark for varying instance sizes, comparing the non-batched
baseline with the batched solution generated by HECO. While the runtime of the
naive version increases linearly with the image size, the batched solution
maintains the same performance (until parameters must be increased to
accommodate even larger images). Instead, the runtime is more closely tied to
the size of the kernel than to that of the image. This highlights the dramatic
transformations achieved by HECO, fundamentally changing the structure of the
program. As a result of these transformation, HECO achieves a speedup of 3454x
over the non-batched baseline for $64x64$ pixel images. demonstrating the
extraordinary impact that effective use of batching can have on FHE
applications: while the non-batched solution is borderline impractical at over
two minutes, the batched solution takes only a fraction of a second (0.04 s).

#### Hamming Distance

The runtime of the generated code in this case does depend directly on the
vector length. However, due to the fold-style optimization (c.f. § 4.3), this
dependence is only logarithmic. In Figure 6(d)/6(b), we can see that, for
realistic problem sizes, the performance advantage of batching becomes
significant, resulting in a speedup of 934x for 4096-element vectors. We also
see that, while the runtime of the batched solution does increase with the
vector length, this is nearly imperceptible when compared to the non-batched
baseline.

#### Compile Time

HECO achieves these fundamental transformations without requiring heavy-weight
approaches such as synthesis. While Porcupine takes just over two seconds for
the hamming distance (for 4-element vectors), it requires more than 10 minutes
to synthesize a batched solution for the Roberts Cross benchmark [40]. In
contrast, HECO’s compile time never exceeds two seconds for either of the two
benchmarks, as can be seen in Table 1.

$n$ |  4 |  16 |  64 |  256 |  1024 |  4096
---|---|---|---|---|---|---
rc |  0.06 |  0.07 |  0.08 |  0.12 |  0.30 |  1.28
hd |  0.03 |  0.04 |  0.06 |  0.09 |  0.25 |  1.85
Table 1:  Compile time (in seconds) of the Roberts Cross (rc) and Hamming
Distance (hd) benchmarks for different problem sizes ($n$).

##  7 Related Work

In this section, we briefly discuss related work in the domain of FHE
compilation.

The EVA compiler [15] offers a user-friendly high-level interface and
automatically inserts ciphertext maintenance operations into the circuit. EVA
uses a circuit-based IR and requires developers to manually map their program
to the FHE programming paradigm. In order to ease this process, recent
versions [14] include a library of expert-implemented batched kernels for
frequently used patterns, e.g., summing all elements in a vector. In contrast,
HECO automatically translates arbitrary non-batched applications into
efficient batched applications, with no involvement of the user.

The Porcupine compiler [40] is closest to our work, in that it also considers
translating imperative programs to FHE’s batching paradigm. However, their
tool has a significantly different focus, using a heavy-weight synthesis
approach that tries to identify optimal solutions that can outperform even
state-of-the-art approaches used by experts. Since it explores a large state
space in the search for an optimal solution, compile times tend to be long (up
to many minutes) and programs can contain at most a handful of statements
before the approach becomes infeasible. Additionally, Porcupine requires that
developers provide a sketch of the structure of the batched program, making it
less suitable for non-expert users.

Tools like Cingulata [12], E3 [13], and Google’s Transpiler [11] translate
their input programs into binary circuits, encrypting each bit of the input
individually. This allows them to translate arbitrary programs, without the
usual restrictions of FHE. However, programs translated in this way are
virtually always too inefficient to be of practical use.

Finally, current domain-specific compilers [43, 9], e.g., targeting encrypted
Machine Learning applications, rely on a large set of hand-written expert-
optimized kernels for common functionality (mostly linear algebra operations).
Since these tools rely on pre-determined mappings rather than automatically
identifying optimization opportunities, they do not transfer to other domains,
such as the general-purpose setting HECO targets.

## Acknowledgments

We thank Gyorgy Rethy and Nicolas Küchler for their assistance in the
evaluation of HECO. This work was supported in part by the SNSF Ambizione
Grant No. 186050 and by Semiconductor Research Corporation (SRC).

## References

  * [1] S. Kannepalli, K. Laine, and R. C. Moreno, “Password monitor: Safeguarding passwords in microsoft edge.” https://www.microsoft.com/en-us/research/blog/password-monitor-safeguarding-passwords-in-microsoft-edge/, 21 Jan. 2021.  Accessed: 2021-7-5.
  * [2] M. Kim, A. O. Harmanci, J.-P. Bossuat, S. Carpov, J. H. Cheon, I. Chillotti, W. Cho, D. Froelicher, N. Gama, M. Georgieva, S. Hong, J.-P. Hubaux, D. Kim, K. Lauter, Y. Ma, L. Ohno-Machado, H. Sofia, Y. Son, Y. Song, J. Troncoso-Pastoriza, and X. Jiang, “Ultrafast homomorphic encryption models enable secure outsourcing of genotype imputation,” Cell systems, vol. 12, pp. 1108–1120.e4, 17 Nov. 2021.
  * [3] S. Carpov, N. Gama, M. Georgieva, and J. R. Troncoso-Pastoriza, “Privacy-preserving semi-parallel logistic regression training with fully homomorphic encryption,” BMC medical genomics, vol. 13, p. 88, 21 July 2020.
  * [4] DARPA, “Data protection in virtual environments (DPRIVE).” https://sam.gov/opp/16c71dadbe814127b475ce309929374b/view, 27 Feb. 2020\.
  * [5] N. Samardzic, A. Feldmann, A. Krastev, S. Devadas, R. Dreslinski, C. Peikert, and D. Sanchez, “F1: A fast and programmable accelerator for fully homomorphic encryption,” in MICRO-54: 54th Annual IEEE/ACM International Symposium on Microarchitecture, MICRO ’21, (New York, NY, USA), pp. 238–252, Association for Computing Machinery, 18 Oct. 2021.
  * [6] T. H. Nguyen, “5 impactful emerging technologies for 2022,” Gartner, Inc., 8 Dec. 2021\.
  * [7] T. Nguyen, D. Casey, E. Goodness, and A. Woodward, “Emerging technologies and trends impact radar: 2022,” tech. rep., Gartner, Inc, 2021\.
  * [8] F. Boemer, Y. Lao, R. Cammarota, and C. Wierzynski, “nGraph-HE: A Graph Compiler for Deep Learning on Homomorphically Encrypted Data,” in Proceedings of the 16th ACM International Conference on Computing Frontiers, CF ’19, (New York, NY, USA), pp. 3–13, ACM, 2019\.
  * [9] F. Boemer, A. Costache, R. Cammarota, and C. Wierzynski, “nGraph-HE2: A High-Throughput framework for neural network inference on encrypted data,” in Proceedings of the 7th ACM Workshop on Encrypted Computing & Applied Homomorphic Cryptography, WAHC’19, (New York, NY, USA), pp. 45–56, Association for Computing Machinery, Nov. 2019.
  * [10] R. Dathathri, O. Saarikivi, H. Chen, K. Laine, K. Lauter, S. Maleki, M. Musuvathi, and T. Mytkowicz, “CHET: an optimizing compiler for fully-homomorphic neural-network inferencing,” in Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation, (New York, NY, USA), pp. 142–156, ACM, 8 June 2019.
  * [11] S. Gorantala, R. Springer, S. Purser-Haskell, W. Lam, R. J. Wilson, A. Ali, E. P. Astor, I. Zukerman, S. Ruth, C. Dibak, P. Schoppmann, S. Kulankhina, A. Forget, D. Marn, C. Tew, R. Misoczki, B. Guillen, X. Ye, D. Kraft, D. Desfontaines, A. Krishnamurthy, M. Guevara, I. M. Perera, Y. Sushko, and B. Gipson, “A general purpose transpiler for fully homomorphic encryption,” CoRR, vol. abs/2106.07893, 2021, /2106.07893.
  * [12] S. Carpov, P. Dubrulle, and R. Sirdey, “Armadillo: A compilation chain for privacy preserving applications,” in Proceedings of the 3rd International Workshop on Security in Cloud Computing, SCC ’15, (New York, NY, USA), pp. 13–19, ACM, 2015.
  * [13] E. Chielle, N. G. Tsoutsos, O. Mazonka, and M. Maniatakos, “Encrypt-Everything-Everywhere: ISA extensions for private computation,” IEEE Transactions on Dependable and Secure Computing, pp. 1–1, 2020.
  * [14] S. Chowdhary, W. Dai, K. Laine, and O. Saarikivi, “EVA improved: Compiler and extension library for CKKS,” in Proceedings of the 9th on Workshop on Encrypted Computing & Applied Homomorphic Cryptography, WAHC ’21, (New York, NY, USA), pp. 43–55, Association for Computing Machinery, 15 Nov. 2021\.
  * [15] R. Dathathri, B. Kostova, O. Saarikivi, W. Dai, K. Laine, and M. Musuvathi, “EVA: An encrypted vector arithmetic language and compiler for efficient homomorphic computation,” in Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation, 27 Dec. 2019.
  * [16] C. Lattner, M. Amini, U. Bondhugula, A. Cohen, A. Davis, J. Pienaar, R. Riddle, T. Shpeisman, N. Vasilache, and O. Zinenko, “MLIR: A compiler infrastructure for the end of moore’s law,” 25 Feb. 2020, arXiv:cs.PL/2002.11054.
  * [17] P. Paillier, “Public-Key cryptosystems based on composite degree residuosity classes,” in Advances in Cryptology — EUROCRYPT ’99, EUROCRYPT, (Prague, Czech Republic), pp. 223–238, Springer, Berlin, Heidelberg, May 1999\.
  * [18] R. L. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems,” Communications of the ACM, vol. 21, pp. 120–126, Feb. 1978.
  * [19] C. Gentry, “Fully Homomorphic Encryption Using Ideal Lattices,” in Proceedings of the 41st Annual ACM Symposium on Symposium on Theory of Computing - STOC ’09, (Bethesda, MD, USA), p. 169, ACM Press, 2009.
  * [20] Z. Brakerski, “Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP,” in Advances in Cryptology – CRYPTO 2012, vol. 7417, pp. 868–886, Berlin, Heidelberg: Springer Berlin Heidelberg, 2012.
  * [21] J. Fan and F. Vercauteren, “Somewhat Practical Fully Homomorphic Encryption,” IACR Cryptology ePrint Archive, vol. 2012, p. 144, 2012.
  * [22] Z. Brakerski, C. Gentry, and V. Vaikuntanathan, “(leveled) fully homomorphic encryption without bootstrapping,” in Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS ’12, (New York, NY, USA), p. 309–325, Association for Computing Machinery, 2012.
  * [23] J. H. Cheon, A. Kim, M. Kim, and Y. Song, “Homomorphic Encryption for Arithmetic of Approximate Numbers,” in Advances in Cryptology – ASIACRYPT 2017, vol. 10624, pp. 409–437, Cham: Springer International Publishing, 2017.
  * [24] C. Boura, N. Gama, M. Georgieva, and D. Jetchev, “Chimera: Combining ring-lwe-based fully homomorphic encryption schemes,” Journal of Mathematical Cryptology, vol. 14, no. 1, pp. 316–338, 2020.
  * [25] W. jie Lu, Z. Huang, C. Hong, Y. Ma, and H. Qu, “PEGASUS: Bridging polynomial and non-polynomial evaluations in homomorphic encryption,” in 2021 IEEE Symposium on Security and Privacy (SP), IEEE, May 2021.
  * [26] I. Chillotti, M. Joye, and P. Paillier, “Programmable bootstrapping enables efficient homomorphic inference of deep neural networks.” Cryptology ePrint Archive, Report 2021/091, 2021.  https://ia.cr/2021/091.
  * [27] M. R. Albrecht, R. Player, and S. Scott, “On the concrete hardness of learning with errors,” Journal of Mathematical Cryptology, vol. 9, 1 Jan. 2015.
  * [28] M. Albrecht, M. Chase, H. Chen, J. Ding, S. Goldwasser, S. Gorbunov, S. Halevi, J. Hoffstein, K. Laine, K. Lauter, S. Lokam, D. Micciancio, D. Moody, T. Morrison, A. Sahai, and V. Vaikuntanathan, “Homomorphic encryption security standard,” tech. rep., HomomorphicEncryption.org, Toronto, Canada, Nov. 2018\.
  * [29] L. Brenna, I. S. Singh, H. D. Johansen, and D. Johansen, “TFHE-rs: A library for safe and secure remote computing using fully homomorphic encryption and trusted execution environments,” Array, p. 100118, 28 Dec. 2021.
  * [30] F. Bourse, R. Del Pino, M. Minelli, and H. Wee, “FHE circuit privacy almost for free,” in Advances in Cryptology – CRYPTO 2016, pp. 62–89, Springer Berlin Heidelberg, 2016.
  * [31] L. Ducas and D. Stehlé, “Sanitization of FHE ciphertexts,” in Advances in Cryptology – EUROCRYPT 2016, Lecture notes in computer science, pp. 294–310, Berlin, Heidelberg: Springer Berlin Heidelberg, 2016.
  * [32] B. Li and D. Micciancio, “On the security of homomorphic encryption on approximate numbers,” in Advances in Cryptology – EUROCRYPT 2021, (Cham), pp. 648–677, Springer International Publishing, 2021.
  * [33] A. Viand, P. Jattke, and A. Hithnawi, “SoK: Fully homomorphic encryption compilers,” in 2021 IEEE Symposium on Security and Privacy (SP), pp. 1166–1182, 2021.
  * [34] P. Aubry, S. Carpov, and R. Sirdey, “Faster homomorphic encryption is not enough: Improved heuristic for multiplicative depth minimization of boolean circuits,” in Topics in Cryptology – CT-RSA 2020, pp. 345–363, Springer International Publishing, 2020.
  * [35] S. Carpov, P. Aubry, and R. Sirdey, “A multi-start heuristic for multiplicative depth minimization of boolean circuits,” in Combinatorial Algorithms, pp. 275–286, Springer International Publishing, 2018.
  * [36] D. W. Archer, J. M. Calderón Trilla, J. Dagit, A. Malozemoff, Y. Polyakov, K. Rohloff, and G. Ryan, “RAMPARTS: A Programmer-Friendly system for building homomorphic encryption applications,” in Proceedings of the 7th ACM Workshop on Encrypted Computing & Applied Homomorphic Cryptography - WAHC’19, (New York, New York, USA), pp. 57–68, ACM Press, 2019.
  * [37] A. Costache, K. Laine, and R. Player, “Evaluating the effectiveness of heuristic worst-case noise analysis in fhe,” in Computer Security – ESORICS 2020, pp. 546–565, Springer, Sept. 2020.
  * [38] I. Iliashenko, “Optimisations of fully homomorphic encryption,” 27 May 2019.  PhD. Thesis, KU Leuven.
  * [39] “Microsoft SEAL (release 3.5),” Apr. 2020.
  * [40] M. Cowan, D. Dangwal, A. Alaghi, C. Trippel, V. T. Lee, and B. Reagen, “Porcupine: A synthesizing compiler for vectorized homomorphic encryption,” in Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation, PLDI 2021, (New York, NY, USA), p. 375–389, Association for Computing Machinery, 2021.
  * [41] S. Larsen and S. Amarasinghe, “Exploiting superword level parallelism with multimedia instruction sets,” SIGPLAN Not., vol. 35, pp. 145–156, 1 May 2000.
  * [42] C. Mendis and S. Amarasinghe, “goSLP: globally optimized superword level parallelism framework,” Proc. ACM Program. Lang., vol. 2, pp. 1–28, 24 Oct. 2018.
  * [43] R. Dathathri, O. Saarikivi, H. Chen, K. Laine, K. Lauter, S. Maleki, M. Musuvathi, and T. Mytkowicz, “CHET: an optimizing compiler for fully-homomorphic neural-network inferencing,” in Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation, (New York, NY, USA), pp. 142–156, ACM, 8 June 2019.

  *[FHE]: Fully Homomorphic Encryption
  *[IRs]: Intermediate Representation
  *[SIMD]: Single Instruction, Multiple Data
  *[BFV]: Brakerski/Fan-Vercauteren
  *[BGV]: Brakerski-Gentry-Vaikuntanathan
  *[CKKS]: Cheon-Kim-Kim-Song
  *[CRT]: Chinese Remainder Theorem
  *[IR]: Intermediate Representation
  *[DSL]: Domain-Specific Language
  *[AST]: Abstract Syntax Tree
  *[SSA]: Static Single Asignment
  *[SEAL]: Simple Encrypted Arithmetic Library