google / google/heir

Analyse the EvalAddCount and KeySwitchCount and Populate N/moduli chain for BGV

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

Description

Main reference: ["Revisiting Homomorphic Encryption Schemes for Finite Fields"](https://eprint.iacr.org/2021/204) and [OpenFHE pke examples readme](https://github.com/openfheorg/openfhe-development/blob/main/src/pke/examples/README.md)

With the modreduce/relinearize strategy introduced in #1126, we can analyse the EvalAddCount and KeySwitchCount, hence determining the noise growth and enabling HEIR to select ring dimension `N` and the moduli chain `qi` according to the paper.

The first step could be using the analysis to determine these _counts_ and when configuring the OpenFHE CryptoContext we can pass these parameters and let OpenFHE determine `N` and `qi`.

Further step could introduce a pass to use these counts to populate `N`/`qi` inside HEIR, which allows more information inside HEIR, allows us to SetFirstModSize/SetScalingModSize for OpenFHE and could benefit the new Lattigo backend (#1159) which allows the user/compiler to specify `N`/`qi` in a more fine grained way.

Further more, instead of OpenFHE specifying only the first/scaling modulus size, the compiler can specify each level modulus size because we can get the AddCount/KeySwitchCount for each level (instead of a global one). This often means a smaller `Q`.

Also, we can optimize the size of special moduli `pi`, and may possibly reduce the ring dimension `N` as the total `QP` is smaller. This mainly refers to Section 6 of ["Optimisations and tradeoffs for HElib"](https://eprint.iacr.org/2023/104)

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.