google / google/heir

Properly support the underlying slot algebra in the compilation pipeline

Open
#1,450 7 comments 0 reactions 0 assignees View on GitHub
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

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.