Open ZenithalHourlyRate opened 6 days ago
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.
cc @AlexanderViand-Intel - do you have opinions on how bgv-to-lwe
is opinionated with which type of key-switching algorithms to use?
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.
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.
@ZenithalHourlyRate do you want to create a PR with the new key types to start from there?
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.
LWEContext
andLWEEvaluationKey
LWEContext
via a pass like the openfhe onelwe.gen_mulkey
andlwe.gen_rotkey
LWEContext
as argument to the entry function andbgv-to-lwe
will extractLweEvaluationKey
from itI 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).