google / google/heir

Implement a simple cost model for FHE computations

Open
#929 3 comments 1 reaction 0 assignees View on GitHub
optimization
Dominant language
MLIR
Stars
906
Forks
171
Avg merge
4d 12h
Merged PRs (30d)
32

Description

Starting this issue so I have a place to jot down notes as I come across relevant information in the literature.

Basically, various passes will eventually need to start making decisions about whether to choose one type of homomorphic operation or another. We should have a cost model (or multiple models) that help quantify these trade-offs. Eventually I think they will boil down to more quantifiable costs per hardware target, but for high level passes it will still be useful to have a relative tradeoff.

To start, the HyPHEN paper Kim-Park-Kim-Kim-Ahn 2023 (https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=10376063) has a table of benchmark CKKS operation times; 64-threads across two 2.35 GHz CPUs, using RNS-CKKS HEaaN, `N=2^16` (see IV.A in the linked paper).

| Op | Runtime (ms) |
| -------- | ------- |
| Add plaintext | 0.169 |
| Add ciphertext | 0.202 |
| Mul plaintext | 0.506 |
| Mul ciphertext | 17.3 |
| Rescale | 3.90 |
| Plaintext rotate | 0.102 |
| Ciphertext rotate | 15.5 |
| Bootstrap | 2160 |

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.