HEIR: A Unified Representation for Cross-Scheme Compilation of Fully Homomorphic Computation

HEIR: A Unified Representation for Cross-Scheme Compilation of Fully Homomorphic Computation

Speakers: Song Bian

Conference: NDSS Symposium

YouTube: N/A

Overview

Fully Homomorphic Encryption (FHE) stands as a cornerstone of secure multi-party computation, enabling computations on encrypted data without ever decrypting it. This powerful cryptographic primitive promises revolutionary applications in privacy-preserving machine learning, secure databases, and outsourced computation, offering advantages like low round complexity and minimal communication bandwidth. However, the widespread adoption of FHE has been severely hampered by two primary challenges: the extreme complexity of designing FHE programs, which often requires deep cryptographic expertise, and the notoriously slow execution times, with complex tasks potentially spanning hours or even days. Furthermore, the performance of an FHE program is highly sensitive to the underlying FHE scheme and data representation, forcing developers into a difficult usability-efficiency trade-off.

The core problem lies in the fragmented landscape of existing FHE compilers, which typically specialize in either arithmetic or logic circuits. Arithmetic compilers, such as those for BFV and CKKS schemes, leverage Single-Instruction-Multiple-Data (SIMD) properties for efficiency in polynomial operations but falter with non-polynomial computations. Conversely, logic compilers, based on TFHE/FHEW-like schemes, excel at arbitrary non-polynomial functions via Look-Up Tables (LUTs) but suffer from poor performance for arithmetic-heavy tasks due to their bit-level operations. This specialization, coupled with the reliance on Domain-Specific Languages (DSLs), creates a steep learning curve for non-experts and makes hybrid computations—common in real-world applications—prohibitively inefficient due to high conversion costs.

HEIR (Homomorphic Encryption Intermediate Representation) emerges as a groundbreaking solution to this dilemma. Presented by Song Bian at the NDSS Symposium, HEIR is a novel compiler framework designed to unify the compilation of FHE programs across diverse schemes. Its primary objective is to make FHE both usable for non-experts, by supporting native C programs, and significantly more efficient than existing approaches, particularly for complex applications involving a mix of arithmetic and logic computations. By automating scheme selection, data representation, and cryptographic parameter management, HEIR dramatically lowers the barrier to entry for FHE development while achieving unprecedented performance gains.

Background

[▶ Watch: Introduction: FHE challenges and HEIR's goal (0:00)]()

To appreciate HEIR's innovations, it is crucial to understand the diverse landscape of FHE schemes and the limitations of prior compilation efforts. FHE schemes broadly fall into two categories, both rooted in lattice-based hardness assumptions like Learning With Errors (LWE) and Ring-LWE (RLWE).

Logic FHE, epitomized by FHEW and TFHE, encrypts individual plaintext bits or small integers. Its defining feature is Programmable Bootstrapping (PBS), an incredibly fast mechanism that allows for the evaluation of arbitrary functions by mapping inputs to outputs via Look-Up Tables (LUTs), effectively refreshing ciphertext noise and enabling unbounded computation depth. This makes Logic FHE functionally complete and adept at handling complex logic and non-polynomial functions. However, arithmetic operations on larger numbers, such as multi-bit addition or multiplication, are inherently slow due to their bit-wise nature.

Arithmetic FHE, encompassing schemes like BFV, BGV, and CKKS, leverages the Single-Instruction-Multiple-Data (SIMD) capabilities of RLWE ciphertexts. These schemes pack multiple plaintext messages into a single ciphertext, enabling efficient element-wise addition and multiplication on vectors. They are highly efficient for linear and polynomial functions but struggle with non-polynomial or logic operations, as these are difficult to express efficiently within polynomial rings. For instance, privacy-preserving sorting on CKKS can be six times slower than on TFHE due to the nature of comparisons.

A critical aspect of Arithmetic FHE is Encoding Methods, which determine how plaintext messages are transformed into polynomials before encryption.

• Slot Encoding (also known as batching) maps input messages to polynomial coefficients using Number Theoretic Transform (NTT) or Discrete Fourier Transform (DFT), facilitating efficient element-wise SIMD operations.
• Coefficient Encoding directly uses plaintext messages as polynomial coefficients. This method is particularly efficient for homomorphic inner products and convolutions, and is used in techniques like CKKS bootstrapping and sample extraction.
• Residue Number System (RNS) is a technique used to manage the growth of ciphertext moduli during homomorphic operations. It decomposes large moduli into a set of smaller, co-prime moduli, allowing arithmetic operations to be performed independently on each component, thereby avoiding costly large-integer arithmetic.

Bridging the gap between Logic and Arithmetic FHE necessitates Ciphertext Conversions.

• SAMPLEEXTRACT allows extracting an element from an RLWE ciphertext (Arithmetic FHE) into an LWE ciphertext (Logic FHE).
• REPACK performs the reverse, packing a set of LWE ciphertexts into a single RLWE ciphertext. While decryption-based REPACK is faster for many ciphertexts, it often sacrifices bit precision. Automorphism-based REPACK offers higher precision but can lead to incompatible encodings. HEIR introduces improvements to high-precision automorphism-based REPACK for smaller numbers of LWE ciphertexts.
• Slot-to-Coefficient and Coefficient-to-Slot Conversions are essential for optimizing linear transformations, as certain operations are significantly faster with specific encoding methods.

Existing FHE compilers predominantly suffer from two major limitations:

1. Specialization: Most compilers are optimized for either arithmetic or logic circuits. Arithmetic compilers like EVA and HECO are fast for polynomial operations but lack support for non-polynomial functions or have limited multiplicative depth. Logic compilers like Transpiler are functionally complete but exhibit severe performance degradation for arithmetic-heavy tasks.
2. DSL Dependence and Conversion Costs: Many compilers rely on Domain-Specific Languages (DSLs), which pose a significant usability barrier for non-experts. Hybrid compilers like E³ attempt to combine schemes but often incur prohibitive conversion costs, negating potential performance gains. Furthermore, most existing compilers overlook optimizations related to coefficient encoding, focusing primarily on slot encodings. This fragmented and inefficient ecosystem highlights the urgent need for a unified, user-friendly, and highly performant FHE compilation framework, a need that HEIR directly addresses.

Key Findings

[▶ Watch: Encoding methods and ciphertext conversions (3:00)]()

HEIR represents a significant leap forward in the field of FHE compilation, delivering a robust framework that fundamentally enhances both the usability and efficiency of homomorphic computation. Its key findings and contributions can be summarized as follows:

• DSL-Free and Functionally Complete: HEIR is the first FHE compiler framework known to be DSL-free and functionally complete, meaning it can compile arbitrary C programs without requiring specialized cryptographic languages. It does not solely rely on Boolean-circuit representation, a critical distinction that significantly improves usability for non-experts. This is achieved through a multi-level Intermediate Representation (IR) framework that intelligently segments and schedules operations across different FHE schemes.
• Automated Type Conversions and Scheme Switching: The framework introduces a novel, automated type conversion system. It seamlessly transforms plaintext C programs into FHE-friendly IR dialects, automatically instantiating corresponding low-level FHE operators. This system tackles the complex challenge of managing programs with interleaved polynomial and non-polynomial functions, dynamically determining when and how to switch between Logic FHE (LWE) and Arithmetic FHE (RLWE) schemes without manual intervention.
• FHE-Specific Code Lowering and Optimization: HEIR incorporates sophisticated optimization passes tailored specifically for FHE. These include algorithms to resolve operator incompatibility, reduce parameter sizes, and minimize the frequency of costly bootstrapping operations. Notable contributions here are the Mini-Repack algorithm for efficient packing of small numbers of LWE ciphertexts, and a novel encoding pass that automatically selects the most efficient encoding method (slot or coefficient) for RLWE ciphertexts based on the computational context.
• Support for Unbounded-Depth FHE Programs: Through a highly effective ciphertext level management procedure, coupled with multi-modulus bootstrapping, HEIR can compile FHE programs of unbounded multiplicative depth. This mechanism intelligently assigns ciphertext levels and schedules bootstrapping operations to refresh noise and prevent computation errors, a crucial capability for real-world, complex applications.
• Exceptional Performance Gains: Comprehensive end-to-end evaluations demonstrate that HEIR-generated programs achieve unprecedented speedups. For complex applications combining both polynomial and non-polynomial functions, HEIR runs 72x to 179x faster than state-of-the-art FHE compilers. Furthermore, it delivers significant performance improvements for purely arithmetic circuit tasks (ranging from 1.4x to 36x speedup) and logic circuit tasks (ranging from 3.2x to 4.1x speedup). These results underscore HEIR's ability to overcome the long-standing usability-efficiency dilemma in FHE.

Technical Deep Dive

[▶ Watch: Limitations of existing FHE compilers (4:00)]()

HEIR's robust architecture is founded on a multi-level Intermediate Representation (IR) framework built upon MLIR (Multi-Level IR). This choice allows for flexible definition of custom IRs as dialects, maintaining high-level semantics while enabling graph-based optimizations at various levels of abstraction. The compilation process within HEIR is structured into a two-stage code-lowering pipeline: the Transformation Stage and the Optimization Stage.

3.1. Transformation Stage: From Plaintext to FHE-Friendly Dialects

The initial stage focuses on converting the input C program into FHE-compatible representations.

1. Program Conversion from Plaintext to Ciphertext: The input C program, initially parsed into high-level MLIR built-in dialects (e.g., mlir::polygeist, mlir::affine, mlir::arith, mlir::func, mlir::memref), is transformed into HEIR's unified fhe dialect. This dialect introduces abstract encrypted data types: FHEFloat, FHEVector, and FHEMatrix, which encapsulate the underlying cryptographic complexities.
2. Incompatible Statement Removal: Statements incompatible with homomorphic computation are identified and transformed. For instance, if/else statements are handled by evaluating all branches and then using a homomorphic multiplexer to select the correct result. for loops with constant lengths are unrolled to facilitate vectorized optimizations. Dynamically-sized loops are currently not supported and will trigger an error.
3. Variable Encryption Check: HEIR automatically determines which variables require encryption. Program inputs are deemed confidential and mapped to encrypted variables. Constants used in computations with encrypted data are also appropriately encoded.
4. Program Segmentation (Operator-based Conversion): This crucial step segments the program into arithmetic and logic regions, mapping operators and data types to corresponding homomorphic representations within the lwe and rlwe dialects.

• Initially, all variables are treated as non-vectorized LWECipher ciphertexts. The compiler then scans the program to identify regions where scheme-switching conversions can leverage the SIMD capabilities of Arithmetic FHE using RLWECipher ciphertexts.
• For programs without vectorized inputs, plaintext operations are directly translated into homomorphic operations in the lwe dialect. If LWECipher variables are operands for multiplication operations, they are converted to RLWE ciphertexts, necessitating SAMPLEEXTRACT and REPACK operators.
• For vectorized inputs, a batching pass (inspired by HECO's Algorithm 2) transforms element-wise operations into batched computations, typically parsing 2D matrix rows as potential RLWE ciphertexts.

1. Mini-Repack Algorithm (Algorithm 1): HEIR introduces a lightweight Mini-Repack algorithm specifically designed for efficiently packing a small number of LWE ciphertexts into an RLWE ciphertext. This algorithm packs a single LWE ciphertext into the 0-th coefficient of an RLWE ciphertext using EvalTr, then rotates the encrypted plaintext into the i-th coefficient using a monomial multiplication, and finally accumulates it. This addresses scenarios where massive parallelism isn't available or needed.
2. Encoding Optimization (Algorithm 4): This pass intelligently determines the most efficient encoding method (slot or coefficient) for RLWE ciphertexts throughout the program, dynamically scheduling encoding-switching conversions as required.

• Initially, all RLWE ciphertexts are assumed to use slot representation.
• The algorithm then identifies program fragments that would benefit from coefficient encoding, particularly patterns involving accumulations and inner products.
• When a "rotate-and-add" pattern (common in slot encoding for inner products) is detected, the code block is replaced by a simpler multiplication between RLWE ciphertexts in coefficient encoding. Encoding-switching conversions are scheduled only if necessary. A cryptographic subtlety is handled: for correct inner product computation with coefficient encoding, one ciphertext's plaintext coefficients must be in reverse order; HEIR allows the client to encrypt this input directly in reverse to avoid costly runtime conversions.

3.2. Optimization Stage: FHE-Specific Optimizations

The second stage focuses on FHE-specific optimizations, primarily cryptographic parameter selection and bootstrapping scheduling, lowering the transformed dialects into bottom-level FHE library operators.

1. Cryptographic Optimization and Ciphertext Level Management (Algorithm 2): This is crucial for compiling unbounded-depth FHE programs. FHE ciphertexts possess a "level" property, where homomorphic multiplications consume these levels (moduli in the RNS chain). Once only one modulus remains, further ciphertext-to-ciphertext multiplications are impossible without noise growth becoming prohibitive.

• HEIR implements a bootstrapping-aware ciphertext level management technique. It first determines a maximum ciphertext level γ (user-defined, typically 4, based on benchmarks).
• The algorithm traverses the program based on the Def-Use chain, calculating the necessary levels for each ciphertext operator. Operations like C2S (coefficient-to-slot) and S2C (slot-to-coefficient) conversions consume two RNS levels, while RLWEMUL consumes one.
• A variable's level is set to the maximum level required by any of its independent uses.
• If a variable's level exceeds γ, a multi-modulus bootstrapping operator (LUT operator) is scheduled to reset its level, ensuring it remains below the predefined threshold and preventing incorrect evaluation due to insufficient bootstrapping.

1. Multi-Modulus Bootstrapping Algorithm (Algorithm 5): This algorithm is invoked to refresh ciphertexts. It transforms an input LWE ciphertext with large noise in a smaller modulus q into a ciphertext with smaller noise in a larger modulus Q. This involves generating bootstrapping keys, defining a look-up table polynomial, initializing test vectors, and performing a blind rotation on a multi-modulus accumulator to output a high-level ciphertext, essential for enabling unbounded-depth computations.

System Design and Architecture

HEIR's overall compilation flow integrates three main modules:

1. Front-End Module: The input C program is initially processed by Polygeist 96, which transforms it into an MLIR module composed of high-level built-in MLIR dialects (mlir::polygeist, mlir::affine, mlir::arith, mlir::func, mlir::memref). This design effectively decouples generic program optimizations from FHE-specific transformations.
2. Middle-End Module: This is the core of HEIR, housing the FHE-specific transformation and optimization passes. It defines a multi-level HEIR IR:

• The fhe dialect (Upper Layer) characterizes FHE operations and semantics, abstracting cryptographic nuances. It defines types like FHEFloat, FHEVector, and FHEMatrix.
• The lwe and rlwe dialects (Lower Layer) explicitly define the low-level semantics of Arithmetic FHE and Logic FHE schemes and their associated encryption parameters, introducing types such as LWECipher, LWECipherVec, LWECipherMat, RLWECipher, and RLWECipherVec.
• HEIR includes a comprehensive set of operators: RLWE Operators (addition, subtraction, multiplication), LWE Operators (addition, subtraction, functional bootstrapping), Conversion Operators (scheme-switching, encoding-switching), and Maintenance Operators (LOAD, STORE).

1. Back-End Module: This module lowers the lwe and rlwe IRs into concrete homomorphic instructions, which are then executed by HEIR's unified bottom-level FHE library, HALO. HALO, in turn, utilizes Microsoft SEAL as a linking library for low-level polynomial operations. The MLIR framework's multi-layer property ensures that HEIR can be extended to target other FHE libraries if needed.

Threat Model: HEIR operates under a standard secure two-party computation setting. The client possesses private data that they wish for a server to compute upon. The server is assumed to be semi-honest, meaning it faithfully executes the protocol but is curious about the encrypted data. The program logic itself is public to the server. All program inputs are considered confidential and are encrypted, while constant values declared within the program are public. A minimal set of DSL lexica can be integrated for explicit public-private data declarations.

Implementation Details: The entire HEIR compiler framework is implemented in C++17, leveraging the MLIR framework compiled with Clang 14.0.0. The front-end uses a revised Polygeist 96. The back-end library, HALO, relies on Microsoft SEAL; performance benchmarks showed that HALO and Microsoft SEAL compiled with Clang++ offered significantly better runtime performance than with GNU G++. HEIR supports a wide range of native C instructions, including arithmetic operations (+, -, *, /), assignment (=), comparisons (==, <, >), array indexing, if/else statements, for loops, and external function calls (which can be mapped to LUTs). For evaluations, HEIR uses parameters providing 128-bit security, with an upper bound for the RLWE ciphertext modulus Q set to 192 bits for efficient CPU execution.

Demo / Proof of Concept

[▶ Watch: HEIR's multi-level IR technical approach (4:30)]()

HEIR's capabilities and performance were rigorously evaluated against leading state-of-the-art FHE compilers, including arithmetic-circuit specialists (EVA 23, HECO 58) and logic-circuit specialists (Transpiler 21). All experiments were conducted on a single core of an Intel Xeon Gold 5318Y processor equipped with 512GB of RAM.

6.1. Arithmetic Circuit Evaluation

HEIR demonstrated superior performance across several fundamental arithmetic applications: inner product, Euclidean distance, matrix-vector multiplication, Boxblur filtering, and Roberts Cross filtering.

• Inner Product and Euclidean Distance: For these operations, HEIR's optimized coefficient encoding technique proved highly effective. Its runtime latency for inner product and Euclidean distance remained largely independent of the number of vector elements (up to the lattice dimension n), a significant advantage over EVA, whose latency grew linearly. HEIR achieved a speedup of 3.4x to 11x over EVA for inner product and 1.4x to 4.5x for Euclidean distance.
• Matrix-Vector Multiplication: HEIR consistently outperformed EVA, achieving a speedup of 2x to 5x.
• Boxblur and Roberts Cross Filtering: While coefficient encoding was not applicable here, HEIR leveraged SIMD batching optimizations to achieve latency comparable to HECO, resulting in a substantial speedup of 21x to 36x over EVA. Notably, Transpiler was excluded from these comparisons due to its impractical performance; it required approximately 6000 seconds to evaluate a 32-element 16-bit vector inner product.

6.2. Logic Circuit Evaluation

HEIR was evaluated against Transpiler 21 on three common logic circuit benchmarks: vector minimum value, vector minimum index, and Fibonacci sequence.

• Runtime Latency: Both HEIR and Transpiler exhibited linear complexity, but HEIR's cross-scheme paradigm significantly outpaced Transpiler's bit-level FHE computation.
• HEIR achieved a speedup of 3.2x over Transpiler for minimum value evaluation.
• For minimum index evaluation, HEIR was 4.1x faster.
• For the Fibonacci sequence program, HEIR achieved a 3.6x speedup. For a Fibonacci sequence with 64 iterations, HEIR successfully invoked the bootstrapping operator 44 times to manage ciphertext levels, showcasing its robust multi-modulus bootstrapping capability.

6.3. End-to-End Applications

To demonstrate real-world applicability, HEIR was tested on two complex end-to-end applications: Data Analysis (filter-aggregation in a homomorphic database) and K-Means clustering.

• Data Analysis: For a database task involving 32 employees, Transpiler required 2.85 hours to complete. HEIR achieved a remarkable speedup of 72x, finishing the same task in just 2.3 minutes.
• Homomorphic K-Means Evaluation: K-Means clustering is a quintessential hybrid application, involving both arithmetic (distance calculations) and logic (minimum distance comparisons).
• For a small dataset (5 data points, 2 centroids, 3 dimensions), HEIR was 179x faster than Transpiler. Crucially, Transpiler failed to compile K-Means for larger datasets (e.g., 10 data points) due to the overwhelming circuit complexity.
• HEIR successfully compiled K-Means on significantly larger datasets, up to 1024 data points with 3 centroids, achieving competitive latency (e.g., 14 hours for 1024 data points). During these computations, HEIR dynamically invoked conversion operators between 390 and 3078 times per K-Means iteration, demonstrating its efficient scheme-switching mechanism.
• Compared to a hand-tuned K-Means implementation based on Open-PEGASUS 3, HEIR's automatically generated programs still achieved comparable runtime latency, highlighting its effectiveness without requiring manual cryptographic expertise.

6.4. Compilation Time and Memory Usage

• Compilation Time: HEIR achieved compilation times comparable to EVA and HECO, typically completing in less than one second. In stark contrast, Transpiler, due to its complex Boolean circuit synthesis, required tens to hundreds of seconds for compilation.
• Memory Usage: For arithmetic circuits, HECO and HEIR exhibited better memory overhead than EVA, primarily due to their advanced batch-related optimizations. For logic and hybrid circuit evaluation, HEIR consumed more memory than Transpiler. This is an intentional trade-off: HEIR utilizes more utility keys (Galois keys, relinearization keys) to significantly accelerate program evaluation at runtime, prioritizing speed over minimal memory footprint in these complex scenarios.

Defensive Implications

[▶ Watch: HEIR's two-stage code-lowering structure (5:00)]()

While the HEIR framework itself does not introduce new vulnerabilities or directly address defensive measures against cryptographic attacks, its profound impact lies in significantly advancing the practical deployment of privacy-preserving technologies through Fully Homomorphic Encryption.

The increased usability, stemming from its DSL-free approach and support for native C programming, drastically lowers the barrier for organizations and developers to integrate FHE into their systems. No longer do they require deep cryptographic expertise to design and implement FHE-enabled applications. Coupled with the demonstrated exceptional efficiency gains (up to 179x faster for complex tasks), HEIR makes FHE a far more viable and attractive solution for real-world secure computation.

For defenders, this means that privacy-preserving applications, previously deemed too complex or too slow for practical use, can now be developed and deployed with greater ease and performance. This enables robust data protection in highly sensitive domains such as healthcare (secure genomic analysis), finance (privacy-preserving fraud detection), and critical infrastructure (secure multi-party threat intelligence sharing). Defenders can leverage HEIR to build systems that perform secure data analytics, train AI models on confidential datasets, or collaborate on sensitive information without exposing the underlying plaintext data. In essence, HEIR transforms FHE from a theoretical promise into a practical tool, empowering defenders to proactively safeguard data privacy and confidentiality in an increasingly data-driven and interconnected world.

Key Takeaways

• HEIR is a pioneering DSL-free FHE compiler that unifies both arithmetic (RLWE) and logic (LWE) FHE schemes, allowing non-experts to program complex homomorphic computations in native C.
• It achieves unprecedented performance, demonstrating speedups of 72x to 179x for end-to-end hybrid applications like K-Means clustering and data analysis, and significant gains (1.4x-36x for arithmetic, 3.2x-4.1x for logic) over state-of-the-art FHE compilers.
• The framework automates critical cryptographic complexities, including scheme switching, dynamic encoding method selection (slot vs. coefficient), and intelligent scheduling of ciphertext conversions and bootstrapping operations.
• HEIR supports unbounded-depth FHE programs through a robust ciphertext level management system and multi-modulus bootstrapping, which effectively refreshes noise and prevents computation errors.
• Its multi-level IR architecture, built on MLIR, provides the flexibility and power necessary for sophisticated cross-scheme program segmentation and operator optimization.
• By lowering the usability barrier and dramatically improving efficiency, HEIR makes Fully Homomorphic Encryption a much more practical and accessible technology for real-world privacy-preserving applications.

About the Speaker(s)

Song Bian is a researcher who presented the HEIR framework at the NDSS Symposium. The transcript does not provide further biographical details such as their title or affiliation.