Properly support the underlying slot algebra in the compilation pipeline
- Dominant language
- MLIR
- Stars
- 906
- Forks
- 171
- Avg merge
- 4d 12h
- Merged PRs (30d)
- 32
Description
Given #1186 and the discussion on ciphertext semantic in layout conversion passes in HEIR meeting, we might want to correctly model the slot-algebra in `bgv` dialect (like `bgv.rotate_dim`), to avoid bad lower dialect semantic affecting earlier layout decision.
We might also want to introduce earlier dialect operation like `tensor_ext.rotate_dim` to correspond to lower FHE scheme semantic. `tensor_ext.permute` can then be lowered to `tensor_ext.rotate_dim`.
Currently, the semantic of `bgv.rotate` is 1-dim rotation of all slots, which is in accordance with our programming intuition, but not (always) in accordance with the underlying slot-algebra.
For the slot-algebra, HElib has a very detailed explanation in Section 3 of [Design and implementation of HElib](https://eprint.iacr.org/2020/1481). In short, it is the plaintext modulus `t` and the cyclotomic order `m` that determines the underlying slot-algebra via the structure of automorphism group.
* For prime `t` and power-of-two `m`, the automorphism group has the structure of `(Zm)* = Zm/4 x Z2`, then the slot can be viewed as a `m/4 x 2` matrix.
* For prime `t` and prime `m`, the automorphism group is `(Zm)* = Z(m-1)`, a cyclic group and the slot can be viewed as a 1 dim vector.
Current FHE libraries commonly consider these two cases, and the first one is more widely adopted. Openfhe/Lattigo only support power of two `m`.
* Extra note is that, even Openfhe BGV support only exposes the API of rotate, its underlying slot-algebra is still m/4 x 2. See https://github.com/google/heir/issues/1186#issuecomment-2542791299
In the meantime, our `LWE` type system does not rule out all possibilities of slot-algebra, so our modeling in `bgv` dialect should be generic enough to embrace these possibilities, or at least these two cases.
Contributor guide
Assessment
This issue has not been assessed yet.