CKKS first modulus selection analysis
- Dominant language
- MLIR
- Stars
- 906
- Forks
- 171
- Avg merge
- 4d 12h
- Merged PRs (30d)
- 32
Description
In working on supporting rolled kernels, I hit an infinite loop in `generate-params-ckks`. The code uses a range analysis in `getExtraBitsForLevel0` to determine how many extra bits are required (above the scaling factor bit size). That range analysis loops infinitely in the presence of loops, which is expected, and I am able to manually set the `first-mod-bits` to avoid this and proceed.
Along the way, I was reading about how the first modulus bit size is typically set. It seems that it is typically the sum of the scaling bit size, plus the bit size of the maximum noise at level 0 (which requires a noise model), plus some number of bits to account for precision loss during CKKS rescaling (which requires bounds on the intermediate values of variables), plus a buffer of ~2 extra bits to account for tails of noise distributions.
This issue is for the task of implementing a more full-fledged analysis here. It should also support loops, with the constraint that loop iterations are mgmt-invariant (this will remove most of the problems except ensuring range analysis doesn't loop infinitely).
Contributor guide
Assessment
This issue has not been assessed yet.