Evaluation key management for lwe dialect

[ZenithalHourlyRate]

bgv.relinearize / bgv.rotate currently can not be lowered to lwe and further polynomial dialect. The problem here is that the lwe dialect lacks the information of the evaluation key for multiplication/rotation.

For lowering to openfhe, it is solved by a --openfhe-configure-crypto-context pass (#696) that creates a !openfhe.crypto_context and it was further passed to other openfhe arithmetic ops.

If we follow the same methodology, it can be breaks down into the following steps.

• Add LWEContext and LWEEvaluationKey
• Configure LWEContext via a pass like the openfhe one
  • Add ops like lwe.gen_mulkey and lwe.gen_rotkey
• Add LWEContext as argument to the entry function and bgv-to-lwe will extract LweEvaluationKey from it

I wonder if this is a desired approach to the problem and want to know maintainer's thoughts about this (I searched about how to materialize relinearize/keyswitching in the issues but found little discussion on it).

[asraa]

Hey! Sorry for the delay last week at the conferences. I'm going to place this on our next meeting notes agenda as well.

LWEEvaluationKey

I agree that we should add key-switching keys to our LWE dialect's types for both relinearization and key-switching after rotation. I think they key should have an identifier on it that describes the key-switching mechanism (it can generally be a key-basis transform like (1, s, s^2) -> (1, s) or we can make it either a relinearization key for multiplications or an evaluation key after rotations that describes (1, s^i) -> (1, s). The latter is probably more simple to read and for the later conversion passes to handle).

Add LWEContext

I'm not totally convinved we need a global context object - but let's figure out what would go in it. I do think we wit ill need to "configure" some global cryptosystem information... but it's not clear to me that it needs a separate object vs can be held in the types for the ciphertext and keys. For e.g, maybe the attributes on the lwe.relinearization_key can hold all of the information we need.

Materializing a key-switching key will unfortunately require making a decision on the algorithm for key-switching used (whether this is an RNS variant of a scheme, the base used to decompose the digits of the ciphertext whether 2 or other low norm base, and the technique). This paper https://eprint.iacr.org/2018/117.pdf (section 2.4) has some descriptions.

So to me we will need to make a decision on what keyswitching method we will use at least for this bgv-to-lwe pass. We can make a decision to chose a single one now too and always configure others later. The likely choice is to use the hybrid key switching from that paper earlier which is used in OpenFHE.

The new LWE types should tell us if we are using RNS variants or not in the scheme. The new relinearization_key type can also hold the base which the key was constructed with, and like the LWE type, the ring / moduli that it holds.

[asraa]

cc @AlexanderViand-Intel - do you have opinions on how bgv-to-lwe is opinionated with which type of key-switching algorithms to use?

[ZenithalHourlyRate]

Materializing a key-switching key will unfortunately require making a decision on the algorithm for key-switching used

I think more liberty can be left here. We can add information to the relinearzation_key on the KeySwitchTechnique (either BV, BV-RNS, GHS, GHS-RNS, HYBRID) used. This is also helpful for openfhe dialect (currently openfhe emitter implicitly uses the HYBRID method). And lwe.relinearize lowering can materialize depend on that information.

[asraa]

Yeah, I mean the lowering pass will have to choose one - in our LWE types we also have an enum specifying the encryption type (MSB/LSB bits of the ciphertext or mixed with error), so I think we should continue to do that.

[asraa]

@ZenithalHourlyRate do you want to create a PR with the new key types to start from there?

[ZenithalHourlyRate]

Certainly. I think the following thing can be a first step: LWE_BVKeySwitchAttr, LWE_HYBRIDKeySwitchAttr (GHS is included in it),NewLWEEvaluationKey and change to KeyAttr where another rotate array is used for rotation key.

Combining the basis/rotate array together, we can express `(1, s, s^2, s(X^2), s^2(X^2))` as `[0, 1, 2, 1, 2]` and `[0, 1, 1, 2, 2]`.

Still working on the params corresponding to the SetDigitSize()/SetNumLargeDigits().

For BV, OpenFHE only allows base (beta in literature) to be 2 ** digitSize (also found a bug on this), or qi by SetDigitSize(0)

For HYBRID, the BV technique inside only allows large digit (dnum in literature).

These corresponds to three levels of gadget decomposition granularity, which should be related to #276.