505 CHLOE Loop Transformation over Fully Homomorphic Encryption via Multi Level Vectorization and Co

### Overview In this talk, Jaozan from Beihang University introduces CHLOE (referred to as Cloy/Chloy in the transcript), an FHE (Fully Homomorphic Encryption) compiler middle-end designed to optimize loop structures. Automating homomorphic computation via FHE compilers is critical to making FHE accessible and practical for non-experts. While standard FHE compilers typically operate across three stages—front-end translation to FHE IR, middle-end rewriting/analysis, and back-end security parameter optimization and library API mapping—CHLOE specifically targets the middle end. It focuses on transforming loops with complex control structures into FHE-friendly representations using multi-level vectorization, loop segmentation, and branch/control reduction.

### Key Topics - **FHE Compiler Architecture**: Splitting compiler workflows into front-end IR translation, middle-end control structure optimization, and back-end parameter/library mapping. - **Transparent Loops vs. Oblivious Loops**: Identifying the distinct challenges of loops with unencrypted control conditions (transparent) versus loops with encrypted conditions and branches (oblivious). - **Loop Segmentation & Vectorization**: Breaking down complex loop bodies into separate logical and arithmetic circuits to enable batched operations. - **Oblivious Loop Handling & Recurrences**: Deriving closed-form expressions for Gosper-summable or C-finite recurrences, and batching condition evaluations when closed forms are not possible.

### Technical Details - **Transparent Loop Optimization**: The main difficulty in transparent loops arises from mixed arithmetic (additions/multiplications) and logical (comparisons) operations, which obstruct vectorization. CHLOE distributes complex loops into separate simple loops containing a single operation type. Pure comparison logic circuits use SIMD programmable bootstrapping for batch comparison, while arithmetic circuits are converted into rotation-based accumulation, enabling vectorized execution. - **Oblivious Loop Optimization**: Oblivious loops cannot determine termination conditions or branch paths at runtime, requiring traversal of all iterations and branches. CHLOE handles these in two ways: 1. If loop bodies match Gosper-summable or C-finite recurrences, a recurrence solver derives closed-form expressions, evaluating exponent terms via blind rotation. 2. For generic oblivious loops, CHLOE applies branch optimization to batch condition evaluations using equality tests (via polynomial approximation or SIMD programmable bootstrapping) or external product-based branch optimization tailored for RGSW ciphertext encoding. - **Benchmarking**: CHLOE was evaluated against compilers such as HEIR, Transpiler, and PEGASUS across arithmetic circuit benchmarks and five oblivious loop applications. It achieved significant latency reductions, especially for benchmarks resolving to closed-form expressions and through branch reduction strategies that avoid per-iteration comparisons.

### Takeaways & Limitations CHLOE demonstrates substantial speedups for loop execution in FHE, but introduces trade-offs. The use of SIMD programmable bootstrapping substantially increases memory usage. Furthermore, loops containing complex nested dependencies limit CHLOE's ability to fully exploit its vectorization techniques. The CHLOE compiler source code is open-sourced and available on GitHub.