google
Investigate How/If "HEILP: An ILP-based Scale Management Method for Homomorphic Encryption Compiler" can be integrated into HEIR
RNS-CKKS, a fully homomorphic encryption (FHE) scheme, enabling secure computation on encrypted data, has widely be used in statistical analysis and data mining. However, developing RNS-CKKS programs requires substantial knowledge of cryptography, which is unfriendly to non-expert programmers. A critical obstacle is the scale management, which affects the complexity of programming and performance. Different FHE operations impose specific requirements on the scale and level, necessitating programmer intervention to ensure the recoverability of the results. Furthermore, operations at different levels have a significant impact on program performance. Existing methods rely on heuristic insights or iterative methods to manage the scales of ciphertexts. However, these methods lack a holistic understanding of the optimization space, leading to inefficient exploration and suboptimal performance. This work proposes HEILP, the first constrained-optimization-based approach for scale management in FHE. HEILP expresses node scale decision and scale management operation inserting as an integer linear programming model which can be solved with existing mathematical techniques in one shot. Our method creates a more comprehensive optimization space and enables a faster and more efficient exploration. Experimental results demonstrate that HEILP achieves an average performance improvement of 1.72xover existing heuristic method, and outperforms a 1.19x performance improvement with 48.65x faster compilation time compared to the state-of-the-art iteration-based method.
https://www.date-conference.com/programme
Looks like a relatively straightforward ILP, though the details are sparse. If the authors have an open source implementation, and it's already in MLIR, it should be straightforward to port.
The (short) paper for this seems to be out now, too: https://ieeexplore.ieee.org/document/10992881
I saw this again today and I'm wondering if @edwjchen has any thoughts on the approach