LWE/RLWE "toolbox" dialect (name tbd)

[j2kun]

This thread is for design discussions around a dialect to house common LWE-like types and operations across scheme dialects (e.g., BGV/CGGI/CKKS).

Context

While I was working on a CGGI dialect, and reviewing the BGV dialect, I realized that we would be re-implementing quite a bit of work across dialects. Each would need:

• An RLWE-like type
• Encoding attributes for encryption/decryption (where in the plaintext is the secret stored, i.e., how many bits are reserved and which end of the plaintext is used)
• Decompositions, etc.

So I started to implement LWE and RLWE dialects separately (starting with LWE in #125), and the discussion arose as to whether there should be one dialect for these or two.

It seems reasonable that, if we design such a dialect correctly, then we can avoid defining ciphertext types in all the scheme-specific dialects, and they can be limited to secret key types that have scheme-specific details. And some ops (like add) can be shared as well.

One type or two?

A central question is whether the LWE and RLWE types within these dialects should actually be a single unified type, akin to the GLWE scheme (G for Generalized) used in much of the CGGI literature. This would work by effectively modeling an LWE type as a GLWE type whose ring attribute's ideal is (x) (setting x=0) to reduce it to the ring of coefficient scalars. This is equivalent-while-squinting to setting a "degree" parameter n to 0, if you are in a setting where the ideal generator is always a cyclotomic polynomial of the form x^n + 1 (n = 0 or n = 2^k for some k), but in HEIR the ring attribute in poly allows for an arbitrary generator.

Aside: the other tunable parameter in GLWE is the number of samples, and some people who write about GLWE call RLWE the "other extreme" (compared to LWE) in which the samples parameter is set to 1 but degree may be arbitrary). Since some CGGI security parameter settings require RLWE ciphertexts with more than 1 sample, I'm not considering that as a 'special' case, and even a separate RLWE type would require a sample-dimension parameter.

I can think of two reasons we might want to keep them separate:

• RLWE may require additional data to be stored on the type that is irrelevant to LWE, likely resulting in those attributes being made optional and making the resulting code to process them more toilsome
• Code to process the types will likely have significant branching, using the attributes to detect the LWE vs RLWE cases, and apply likely entirely different optimizations and lowerings for those cases. This is not necessarily bad, though it could lead us down a path of "two passes in a trenchcoat" that adds more complexity.

Encoding

As in the LWE draft, this dialect will own an attribute that specifies the details of the encoding of a cleartext into a plaintext.

For GLWE-as-LWE this is:

• the plaintext type/bit width
• the cleartext type/bit width (I'm pretty sure all LWE variants have the cleartext in the top-most bits)
• the number of bits reserved for padding. For general LWE this is 0, for CGGI it must be 1 for bootstrapping.

For GLWE-as-RLWE this is:

• the plaintext & cleartext type/bit widthprimes
• where in the plaintext the cleartext is stored (is this always a "MSB/LSB" binary choice?)
• the list of moduli for an RNS decomposition (is this part of the encoding or a wholly separate attribute? not sure)

Noise

It seems like the concept of ciphertext noise tracking could be centralized in this dialect. We could start by having:

• a NoiseDistribution attribute (say, start with Gaussian and generalize to an interface later) that could be shared across schemes to represent the

I'm not sure what else, since we tentatively agreed that the noise bounds/models would be computed via an analysis pass, that is not tied to the dialect itself.

Do encode/decode & encrypt/decrypt ops belong here?

I think they could, but that some schemes would have additional scheme-specific ops. For example, CGGI has a GSW key for its bootstrapping key, which boils down to a list of standard RLWE encryptions arranged in a special way. The GSW part would live in the cggi dialect, and it would lower to this dialect.

If encrypt/decrypt lives here in some form, then so would the basic form of the key types. Not sure if any ops like modulus switch or key switch could be generalized to live here. In CGGI at least, the LWE key switch and modulus switch are not CGGI-specific.

What to name this dialect?

Options that have been floated so far are:

• glwe
• lattice
• lwe (just declare that "LWE" means the more general version)

My personal favorite is lwe because it reduces the sort of acronym headache that comes with a new project, and it's quite common in math to reuse names for generalized versions of original concepts.

[j2kun]

Main alternative floated here is to represent the LWE/RLWE types as tensors with custom attributes (since tensor allows one to put arbitrary custom attributes on the type) to represent the encoding.

[j2kun]

I think no matter what there is a need for attributes describing encoding, so working on that in #161