CHLOE: Loop Transformation over Fully Homomorphic Encryption via Multi-Level Vectorization and Control-Path Reduction

CHLOE: Loop Transformation over Fully Homomorphic Encryption via Multi-Level Vectorization and Control-Path Reduction

Speakers: Song Bian, Zian Zhao, Ruiyu Shen, Zhou Zhang, Ran Mao, Dawei Li (from Behan University)

Conference: IEEE S&P

YouTube: https://www.youtube.com/watch?v=-_cS4oDe0HE

Overview

The talk introduces CHLOE, an innovative compiler designed to significantly enhance the efficiency of programs leveraging Fully Homomorphic Encryption (FHE) by addressing one of FHE's most challenging computational bottlenecks: loops. Fully Homomorphic Encryption is a groundbreaking cryptographic primitive that allows computations to be performed directly on encrypted data without ever decrypting it, thus preserving data privacy even when processed by untrusted third parties, such as cloud providers. However, the inherent complexity of FHE operations often leads to substantial performance overhead, making its practical adoption difficult for real-world applications. CHLOE focuses on mitigating this overhead, particularly for programs containing complex loop structures and conditional branches, which are notoriously inefficient in the FHE paradigm.

Developed by a team from Behan University, CHLOE operates as a "middle-end" component within the FHE compiler workflow. Its primary contribution lies in its sophisticated techniques for multi-level vectorization and control-path reduction. By intelligently transforming loop bodies and optimizing branch evaluations, CHLOE aims to make homomorphic computation more accessible and usable for non-experts. This is crucial because, without advanced compiler optimizations, developers would need deep expertise in FHE mathematics and cryptographic engineering to write performant homomorphic programs, thereby limiting FHE's widespread applicability.

The significance of CHLOE lies in its direct attack on a core practical barrier to FHE adoption. While FHE offers unparalleled privacy guarantees, its computational cost has been a major impediment. By providing a compiler that can automatically and efficiently translate standard programming constructs like loops into FHE-friendly operations, CHLOE lowers the entry barrier for FHE development. This work is vital for advancing the state of privacy-preserving computation, enabling a future where sensitive data can be processed in the cloud with strong cryptographic assurances, unlocking new possibilities for secure analytics, machine learning on encrypted data, and confidential cloud services.

Background

▶ Watch: Introduction to FHE compilers and Chloe's focus (0:00)

The concept of an FHE compiler is central to making Fully Homomorphic Encryption practical and accessible. An FHE compiler acts as a bridge, translating conventional programs (often written in languages like C) into a form suitable for homomorphic execution. The typical workflow of an FHE compiler is divided into three main stages. The front-end is responsible for parsing the input program and translating it into an intermediate representation (IR) that captures the program's logic. The back-end then takes this transformed program, optimizes parameters (e.g., security levels, noise budgets), and maps the operations to specific APIs provided by FHE libraries (e.g., SEAL, HElib, TFHE).

CHLOE, however, primarily focuses on the middle-end of this compiler workflow. This critical stage involves rewriting the program's IR into a more FHE-friendly form, specifically by analyzing and transforming its control structures. The necessity for such a middle-end optimization arises from fundamental challenges inherent in FHE. In FHE, all operations are performed on ciphertexts, and the underlying mathematical structures (typically polynomial rings) do not inherently support branching or dynamic control flow based on encrypted data. This means that traditional programming constructs like if-else statements and for or while loops, especially those with conditions dependent on encrypted values, become extremely inefficient or even impossible to implement directly.

The core problem CHLOE addresses is the inefficiency of loops, particularly those with complex branch structures, within the FHE programming paradigm. The talk categorizes these challenging loops into two main types:

1. Transparent Loops: These are loops where the loop condition (e.g., the number of iterations) is not encrypted. An example would be for (i=0; i<n; i++) where n is a publicly known (plaintext) value. While the loop condition itself is transparent, the difficulty in processing transparent loops stems from the potential mix of different types of operations within the loop body. A single loop iteration might involve both arithmetic operations (additions, multiplications) and logical operations (comparisons). This heterogeneity makes it challenging to apply efficient vectorization techniques, which thrive on uniform operations that can be batched together.

1. Oblivious Loops: These represent a more significant challenge. In oblivious loops, the loop condition or branch paths are dependent on encrypted data. For instance, while (encrypted_condition) or an if (encrypted_value > threshold) statement inside a loop. The primary difficulty here is the inability to determine loop termination or which branch path to take without decrypting the sensitive data, which would violate privacy. To maintain obliviousness, FHE programs must, in essence, traverse all potential iterations and evaluate all possible branch paths, masking the results based on the true (but encrypted) condition. This "evaluate all paths" approach leads to a massive computational overhead, as resources are consumed for computations that are ultimately discarded.

Existing FHE compilers and frameworks, such as Hair, Transpeller, and Pexus (mentioned in the benchmark comparison), have made strides in optimizing FHE computations. However, the CHLOE project identifies that the specific and nuanced challenges posed by complex loop structures and conditional logic in FHE programs remain a significant area for improvement. Prior works often struggle with the dual demands of maintaining obliviousness while simultaneously achieving high performance for these control-flow-heavy constructs.

Key Findings

▶ Watch: Chloe's transparent loop optimization via segmentation (3:00)

CHLOE introduces a suite of innovative optimizations specifically designed to tackle the performance bottlenecks associated with loops in Fully Homomorphic Encryption. The key findings and contributions of this work demonstrate a significant leap forward in making FHE practical:

1. Superior Performance Across Benchmarks: Through rigorous benchmark evaluations against established FHE compilers like Hair, Transpeller, and Pexus, CHLOE consistently demonstrates significantly improved performance, particularly for arithmetic circuit benchmarks. This substantial speedup is a direct testament to the effectiveness of CHLOE's novel loop transformation and vectorization techniques.

1. Effective Loop Segmentation and Vectorization: CHLOE's core innovation lies in its ability to apply loop segmentation and vectorization techniques to transform complex loop bodies. By decomposing intricate loops into simpler, homogeneous segments (e.g., separating logical operations from arithmetic operations), CHLOE facilitates the batch processing of operations, a cornerstone of efficient FHE computation. This multi-level approach to vectorization is a primary driver of its performance gains.

1. Optimized Oblivious Loop Handling: For the more challenging oblivious loops (where conditions are encrypted), CHLOE achieves better latency performance compared to other compilers. This is particularly notable because other compilers often require comparison operations in every iteration, leading to substantial overhead. CHLOE's branch reduction strategy minimizes these repetitive and costly operations.

1. Specialized Techniques for Diverse Loop Scenarios: CHLOE offers tailored optimization strategies based on the nature of the loop:

• For transparent loops, it leverages SIMD programmable bootstrapping for batch comparisons in logical circuits and rotation-based accumulation for arithmetic circuits.
• For oblivious loops, it employs a recurrence solver for loops transformable into Gosper summable or cite recurrences, evaluating exponent terms via blind rotation.
• For generic oblivious loops, it introduces equality test based branch optimization (using polynomial approximation or SIMD programmable bootstrapping) and external product-based branch optimization (effective for RGSW ciphertext encoding).

1. Practical Accessibility of FHE: By automating these complex transformations and optimizations, CHLOE makes FHE more accessible to non-experts. The compiler allows developers to write programs with standard loop constructs, abstracting away the intricate FHE-specific requirements and enabling the use of FHE in a wider array of applications without deep cryptographic expertise.

1. Identified Limitations and Future Work: The project openly acknowledges certain limitations, such as increased memory usage when employing SIMD programmable bootstrapping and reduced effectiveness of vectorization for loops with complex nested dependencies. This transparency highlights ongoing research directions to make CHLOE even more robust and efficient.

Technical Deep Dive

▶ Watch: Oblivious loop optimization strategies and techniques (4:30)

CHLOE's technical contributions are primarily situated in the middle-end of the FHE compiler workflow, focusing on sophisticated program rewriting techniques to optimize loop execution. This involves deep analysis of control structures and their transformation into an FHE-friendly format. The fundamental challenge stems from the fact that FHE operates on ciphertexts (encrypted data) and does not natively support dynamic control flow or branching based on encrypted values. Any conditional logic or loop termination criteria dependent on encrypted data must be evaluated "obliviously," meaning all possible paths are computed, and the correct result is selected later, leading to significant overhead.

FHE Compiler Middle-End Focus

The FHE compiler typically translates an input program into an intermediate representation (IR). CHLOE takes this IR and applies FHE-specific transformations and optimizations. A key example is transforming n plaintext multiplications into a single multiplication on ciphertexts, a common FHE optimization that leverages SIMD-like operations on packed ciphertexts. CHLOE extends this principle to complex control flow.

Transparent Loop Optimization

For transparent loops, where the loop condition is public (plaintext), the main challenge is the mixture of arithmetic and logical operations within the loop body, which hinders vectorization. CHLOE's approach is loop segmentation:

1. Decomposition: A complex loop body is decomposed into multiple simpler loops, each containing only a single type of operation. For instance, a loop body mixing comparisons and arithmetic can be segmented into a "logic part" and an "arithmetic part."
2. Logic Circuit Loop: This segment contains purely comparison operations. To enable batch comparison, CHLOE introduces the SIMD programmable bootstrapping technique. Bootstrapping is an FHE operation that refreshes the "noise" in a ciphertext, allowing further computation. SIMD (Single Instruction, Multiple Data) programmable bootstrapping extends this by allowing arbitrary functions (like comparison functions) to be applied to multiple encrypted values packed into a single ciphertext during the bootstrapping process. This allows CHLOE to perform batch comparisons efficiently, rather than sequential, costly comparisons.
3. Arithmetic Circuit Loop: This segment contains purely arithmetic operations (additions, multiplications). This can be transformed into a classic rotation-based accumulation procedure. In FHE, rotation operations on ciphertexts allow rearranging elements within a packed ciphertext. By carefully scheduling rotations and additions/multiplications, CHLOE can vectorize the arithmetic computations, effectively performing multiple arithmetic operations in parallel on a single ciphertext.

This multi-level vectorization through segmentation significantly improves performance by allowing FHE libraries to process operations in large batches.

Oblivious Loop Optimization

Oblivious loops, where loop conditions or branch paths depend on encrypted data, present a more profound challenge. CHLOE addresses this with two main strategies:

1. Close-Form Expression Derivation

If a loop body can be transformed into a Gosper summable or cite recurrence, CHLOE employs a recurrence solver to derive a close-form expression for the loop's result.

• Gosper's algorithm is a method for finding hypergeometric closed forms for sums. A recurrence relation describes a sequence where each term is defined as a function of the preceding ones. If a loop's cumulative effect can be expressed as such a recurrence, a closed-form solution (an expression that directly computes the final result without iteration) can drastically reduce computation.
• For these closed-form expressions, particularly those involving exponent terms, CHLOE evaluates the exponent using blind rotation. Blind rotation is an advanced FHE technique used to perform arbitrary polynomial evaluations on encrypted data without revealing the input or output. This allows the compiler to compute complex functions (like powers) on encrypted data much more efficiently than iterative multiplication. Programs amenable to this transformation run "extremely fast" on CHLOE.

2. Generic Oblivious Loop Branch Optimization

For generic oblivious loops that cannot be reduced to closed-form expressions, CHLOE proposes two approaches for branch optimization, aiming to batch the evaluation of loop conditions and reduce the number of comparison operations per iteration:

• Equality Test Based Branch Optimization: This technique is used for evaluating conditions that involve equality tests (e.g., if (x == y) where x and y are encrypted). It can be implemented through:
• Polynomial Approximation: Complex functions like comparisons (which are non-linear or piecewise) can be approximated by high-degree polynomials. FHE is highly efficient at polynomial evaluation. By approximating the equality test with a polynomial, the comparison can be performed homomorphically.
• SIMD Programmable Bootstrapping: Similar to its use in transparent loops, this technique can be used here to perform batch equality tests or other simple comparisons during the bootstrapping process, effectively evaluating multiple conditions in parallel.

• External Product Based Branch Optimization: This approach is particularly effective for RGSW ciphertext encoding. RGSW (Ring-GSW) is a specific type of FHE ciphertext that allows for very efficient homomorphic evaluation of certain functions, especially those that can be expressed as additions and multiplications of ciphertexts by plaintexts. An "external product" in this context typically refers to multiplying an RGSW ciphertext by another ciphertext or a plaintext value. By structuring branches to leverage the properties of RGSW ciphertexts and their efficient external products, CHLOE can evaluate conditional logic more efficiently, reducing the need for costly comparison operations in every iteration.

In essence, CHLOE's deep dive into loop transformation involves dissecting the loop's nature (transparent vs. oblivious), categorizing its internal operations (logic vs. arithmetic), and then applying highly specialized FHE-native techniques like SIMD programmable bootstrapping, rotation-based accumulation, recurrence solving with blind rotation, polynomial approximation, and RGSW-optimized external products. This multi-faceted approach allows CHLOE to achieve unprecedented performance gains by transforming inherently sequential and conditional operations into batch-parallel, FHE-optimized computations.

Demo / Proof of Concept

▶ Watch: Benchmarking oblivious loop performance and branch reduction (5:40)

While the talk did not feature a live, interactive code demonstration, the efficacy of CHLOE was rigorously proven through a comprehensive benchmark evaluation section. This section served as the primary proof of concept, illustrating CHLOE's performance advantages over existing FHE compilers.

The evaluation process involved comparing CHLOE against three prominent FHE compilers: Hair, Transpeller, and Pexus. The benchmarks were conducted across two main categories of applications, directly corresponding to the types of loops CHLOE targets:

1. Arithmetic Circuit Benchmarks: For programs primarily involving arithmetic operations within loops (often transparent loops or those where arithmetic dominates), CHLOE was evaluated. The results indicated that CHLOE significantly outperforms the other works. This improved performance was explicitly attributed to CHLOE's innovative loop segmentation and vectorization techniques, which enable more efficient batch processing of arithmetic operations on ciphertexts.

1. Oblivious Loop Benchmarks: To assess CHLOE's effectiveness for loops with encrypted conditions, benchmarks were run on "five different applications." These applications likely included programs that could derive close-form expressions (Gosper summable or cite recurrences) and more generic oblivious loops.

• For programs where close-form expressions could be derived, CHLOE demonstrated extremely fast execution speeds. This highlights the power of the recurrence solver and blind rotation techniques, which effectively transform iterative computations into single, direct computations.
• For the other, more generic oblivious benchmarks, where other compilers typically require expensive comparison operations in every iteration, CHLOE's branch reduction strategy achieved better latency performance. This indicates that CHLOE's methods for batching loop condition evaluations (e.g., polynomial approximation, SIMD programmable bootstrapping, external product-based optimization) successfully minimized the overhead associated with oblivious branching.

The presentation of these benchmark results served as a compelling demonstration of CHLOE's capabilities. By quantitatively showing the latency reductions and performance improvements across diverse FHE program types, the speakers provided concrete evidence that CHLOE's multi-level vectorization and control-path reduction strategies translate into tangible, real-world performance benefits, thereby validating its design and implementation. The availability of the CHLOE compiler's source code on GitHub further underscores its status as a verifiable and reproducible proof of concept.

Defensive Implications

▶ Watch: Conclusion, paper, and GitHub source code (6:30)

CHLOE, as a compiler optimization for Fully Homomorphic Encryption, doesn't directly address typical cybersecurity defensive measures like patching vulnerabilities or detecting intrusions. Instead, its defensive implications are foundational, focusing on enabling and enhancing data privacy as a proactive defense mechanism.

1. Enabling Practical Privacy-Preserving Computation: The most significant defensive implication is CHLOE's role in making FHE more practical and performant. FHE is a powerful tool for data privacy, allowing computations on encrypted data without decryption. This means sensitive information can be processed in untrusted environments (like public clouds) without exposing the raw data, thereby mitigating risks of data breaches, insider threats, and unauthorized access. By making FHE faster and easier to use, CHLOE removes a major barrier to its adoption, effectively expanding the defensive perimeter of data privacy.

1. Facilitating Secure Cloud Adoption: Organizations are increasingly moving sensitive workloads to the cloud. While cloud providers offer various security controls, the fundamental concern of data confidentiality during processing remains. FHE, augmented by CHLOE's optimizations, allows enterprises to leverage cloud scalability and cost-effectiveness for tasks like secure analytics, machine learning on encrypted datasets, and confidential AI model inference, all while maintaining strong cryptographic guarantees over their data. This represents a significant defensive posture against data exposure in cloud environments.

1. Reducing Exposure to Side-Channel Attacks: In traditional computing, processing sensitive data often leaves traces in memory or CPU caches that could be exploited by side-channel attacks. FHE, by operating on encrypted representations, inherently reduces the interpretability of such traces. While FHE itself has its own side-channel considerations, the goal of oblivious computation (where the execution path does not depend on the sensitive data) is a core defensive principle. CHLOE's optimizations, particularly for oblivious loops and branch reduction, reinforce this by minimizing information leakage through control flow, even if the underlying FHE operations are still subject to analysis.

1. Lowering the Barrier for Secure Development: Without compilers like CHLOE, implementing FHE applications requires deep cryptographic expertise, making secure development challenging and error-prone. By automating complex loop transformations and FHE-specific optimizations, CHLOE allows developers to write more standard code, reducing the likelihood of implementation errors that could inadvertently compromise privacy. This empowers a broader range of developers to build privacy-preserving applications, strengthening the overall defensive ecosystem.

1. Advancing the State of Privacy Technology: CHLOE contributes to the ongoing research and development in FHE, pushing the boundaries of what is computationally feasible with encrypted data. This continuous advancement is crucial for staying ahead of evolving threats to data privacy and ensuring that cryptographic tools remain robust enough to protect against future adversaries.

In summary, CHLOE does not offer a patch or a firewall, but it fortifies the foundation of data privacy itself. By making FHE a more viable and efficient technology, it provides a powerful, proactive defensive mechanism that enables organizations to protect their most sensitive data throughout its lifecycle, particularly during computation in untrusted environments.

Key Takeaways

• CHLOE is a middle-end compiler for Fully Homomorphic Encryption (FHE) specifically designed to optimize the performance of programs containing loops.
• It addresses the inherent inefficiencies of loops in the FHE paradigm by employing multi-level vectorization and control-path reduction techniques.
• CHLOE distinguishes between transparent loops (plaintext conditions) and oblivious loops (encrypted conditions), applying tailored optimization strategies for each.
• For transparent loops, it uses loop segmentation to separate logical and arithmetic operations, leveraging SIMD programmable bootstrapping for batch comparisons and rotation-based accumulation for vectorized arithmetic.
• For oblivious loops, it employs recurrence solvers with blind rotation for close-form expressions and branch reduction strategies (e.g., polynomial approximation, SIMD programmable bootstrapping, external product-based optimization for RGSW ciphertext encoding) to minimize costly comparison operations.
• Benchmarking against Hair, Transpeller, and Pexus demonstrates that CHLOE significantly outperforms other compilers, achieving faster execution and better latency, especially for programs amenable to close-form expression derivation.
• While significantly improving performance, CHLOE notes limitations such as increased memory usage with SIMD programmable bootstrapping and reduced effectiveness for loops with complex nested dependencies.

About the Speaker(s)

The talk was presented by Jaozan (likely Zian Zhao) from Behan University, representing a team of researchers including Song Bian, Ruiyu Shen, Zhou Zhang, Ran Mao, and Dawei Li. The collective expertise of the speakers from Behan University is focused on advancing the field of Fully Homomorphic Encryption, particularly in compiler design and optimization. Their work with CHLOE demonstrates a deep understanding of the computational challenges inherent in FHE and a commitment to developing practical solutions that make privacy-preserving computation more accessible and efficient for a wider range of applications and users. Their research aims to bridge the gap between theoretical cryptographic guarantees and real-world performance requirements, pushing FHE closer to widespread adoption.