LWE: distinguish ct-pt mul and ct-scalar mul
- Dominant language
- MLIR
- Stars
- 906
- Forks
- 171
- Avg merge
- 4d 12h
- Merged PRs (30d)
- 32
Description
In LWE dialect, we have ct-ct multiplication already, ct-pt multiplication modeled in bgv/ckks dialect. I propose we should also support ct-scalar mul (some literature also call it ct-constant mul)
### All those multiplication
For a **ct** of form (-**as** + **m** + **te**, **a**), where bold letter means it is a ring element (or vector), we have the following possible way to multiply it
* Tensor product: tensor product by another ciphertext **ct**'
* Multiply by a ring element in `Zt[X]/(X^N + 1)`, like **m**': the result becomes (-**asm**' + **mm**' + t**em**', **am**')
* Multiply by a scalar in Zt, like k: the result becomes (-k**as** + k**m** + tk**e**, **a**k)
### Different lowering
For `arith.mul %ct, %c2` where `%c2 = arith.constant 2`, to correctly lowering, we have the following ways
* encrypt 2 to get **ct**' and do ct-ct multiplication
* splat 2 into a vector `[2, 2, ...]` and properly encode (full crt encoding or inverse canonical encoding) it into **m**', then do ct-pt multiplication
* directly do ct-scalar
### Different noise behavior
One benefit of the modelling of ct-scalar mul is that, it has much smaller noise growth. For the multiplying by 2 example, we have the noise term of t**em** and tk**e** respectively. Of course the latter is much friendly.
Note that the overflow of [**mm'**]_t into noise also counts.
### Cases where ct-scalar mul is wanted
In polynomial approximation output, there would be a lot of ct-scalar multiplication, if we instead just use ct-pt version, the noise growth would be quite unexpected.
Specificially, the sine function approximation in CKKS bootstrapping needs ct-scalar multiplication, and if we do not control the noise/precision carefully, the result could be unexpected.
For scale management, the adjust scale operation is also a ct-scalar multiplication.
### Backend supports such difference
For Openfhe, they offer three sets of API
```
EvalMul(ct, ct)
EvalMul(ct, pt)
EvalMul(ct, NativeInteger constant) or double constant for CKKS
```
For Lattigo, it also supports three sets of API, accepting either rlwe ct, vector of input, and a scalar.
Contributor guide
Assessment
This issue has not been assessed yet.