一句话：提出 HEaaN.MLIR 编译器与 Poly/ModArith IR，跨多项式运算优化，最高实现 4.55 倍提速。
环基同态加密以多项式环上的算术为基本构件。现有优化方式各有局限：一方面加速底层多项式运算，但无法跨多个多项式运算进行融合优化；另一方面以手工融合方式实现高度优化的 HE 运算，性能虽好却难以维护。本文提出 HEaaN.MLIR 编译器，以及面向整数多项式算术与整数数组模算术的两个中间表示 Poly 和 ModArith，支持跨多项式运算的优化。这些优化源自 HE 开发者手工优化的经验，包括模算术运算优化、循环融合与整数算术指令向量化。编译器可解析由 Poly 与 ModArith 指令组成的程序，并为 CPU 生成高性能多线程机器码。实验表明，编译后的运算在单线程下最高比高度优化的开源和商业 HE 库快 3.06 倍，多线程下最高快 4.55 倍。
Homomorphic encryption (HE) is an encryption scheme that provides arithmetic operations on the encrypted data without doing decryption. For Ring-based HE, an encryption scheme that uses arithmetic operations on a polynomial ring as building blocks, performance improvement of unit HE operations has been achieved by two kinds of efforts. The first one is through accelerating the building blocks, polynomial operations. However, it does not facilitate optimizations across polynomial operations such as fusing two polynomial operations. The second one is implementing highly optimized HE operations in an amalgamated manner. The written codes have superior performance, but they are hard to maintain. To resolve these challenges, we propose HEaaN.MLIR, a compiler that performs optimizations across polynomial operations. Also, we propose Poly and ModArith, compiler intermediate representations (IRs) for integer polynomial arithmetic and modulus arithmetic on integer arrays. HEaaN.MLIR has compiler optimizations that are motivated by manual optimizations that HE developers do. These include optimizing modular arithmetic operations, fusing loops, and vectorizing integer arithmetic instructions. HEaaN.MLIR can parse a program consisting of the Poly and ModArith instructions and generate a high-performance, multithreaded machine code for a CPU. Our experiment shows that the compiled operations outperform heavily optimized open-source and commercial HE libraries by up to 3.06x in a single thread and 4.55x in multiple threads.
@article{paperbot2010,
title = {HEaaN.MLIR: An Optimizing Compiler for Fast Ring-Based Homomorphic Encryption},
author = {Sunjae Park and Woosung Song and Seunghyeon Nam and Hyeongyu Kim and Junbum Shin and Juneyoung Lee},
journal = {Proceedings of the ACM on Programming Languages},
volume = {7},
number = {PLDI},
year = {2023},
doi = {10.1145/3591228}
}