一句话：提出性能感知的静态 scale 分析，通过 reserve 预算反向重分配，无需空间探索即可生成高效尺度管理方案。
RNS-CKKS 全同态加密（FHE）支持在密文上做定点计算，是实现隐私保护机器学习的可行方案，但其程序编写需要手动管理 scale：每个密文有 scale 值与最大 scale 容量，乘法会增大 scale，程序员必须适当 rescale 以同时降低 scale 与容量。现有编译器虽能自动分析与管理密文 scale，但要么保守地 rescale 而放弃进一步优化机会，要么需要耗时的尺度管理空间探索。本文提出一种新的性能感知静态 scale 分析，无需昂贵的空间探索即可生成高效的尺度管理方案。该方法从程序末尾以反向方式分析每个密文的 scale 预算（称为 reserve），并将预算重新分配给密文，从而实现性能感知的尺度管理；同时设计了新的类型系统来保证分析结果的正确性。评估显示，相比使用保守静态尺度分析的 EVA，本方法取得 41.8% 的性能提升；与基于探索的 Hecate 性能相近，但尺度管理时间快 15526 倍。
Thanks to the computation ability on encrypted data and the efficient fixed-point execution, the RNS-CKKS fully homo-morphic encryption (FHE) scheme is a promising solution for privacy-preserving machine learning services. However, writing an efficient RNS-CKKS program is challenging due to its manual scale management requirement. Each cipher-text has a scale value with its maximum scale capacity. Since each RNS-CKKS multiplication increases the scale, programmers should properly rescale a ciphertext by reducing the scale and capacity together. Existing compilers reduce the programming burden by automatically analyzing and managing the scales of ciphertexts, but they either conservatively rescale ciphertexts and thus give up further optimization opportunities, or require time-consuming scale management space exploration. This work proposes a new performance-aware static scale analysis for an RNS-CKKS program, which generates an efficient scale management plan without expensive space exploration. This work analyzes the scale budget, called "reserve", of each ciphertext in a backward manner from the end of a program and redistributes the budgets to the cipher-texts, thus enabling performance-aware scale management. This work also designs a new type system for the proposed scale analysis and ensures the correctness of the analysis result. This work achieves 41.8% performance improvement over EVA that uses conservative static scale analysis. It also shows similar performance improvement to exploration-based Hecate yet with 15526× faster scale management time.
@inproceedings{0001C0L024,
title = {Performance-aware Scale Analysis with Reserve for Homomorphic Encryption},
author = {Yongwoo Lee and Seonyoung Cheon and Dongkwan Kim and Dongyoon Lee and Hanjun Kim},
booktitle = {ASPLOS},
year = {2024},
doi = {10.1145/3617232.3624870}
}