Encoding "Taxonomy"

[AlexanderViand-Intel]

In order to avoid cluttering up the discussion of #762 (Enc/Dec and Randomness handling), I figured I'd create a new issue to (a) help myself get my thoughts straight on the various mappings/encodings and (b) get some feedback, especially with regards to the TFHE perspective on RLWE.

1. Application Data (e.g. i32) vs. "Cleartext" (e.g. $\mathbb{F}_p$) Semantics

Not sure if "Cleartext" is the right name here, but we usually have a disconnect between the semantics of the actual data type in the application (e.g., i32 or f32) and what we actually end up achieving under HE (usually finite field arithmetic with prime modulus). I know this isn't the case when we do bit-wise encryption (be it in TFHE or in BFV/BGV) but I'm not sure how 4-bit TFHE works here. Clearly, it's something to consider for "word-wise" FHE like BGV/BGV and especially CKKS, with its approximate nature.

Of course, for many applications, the difference between computation mod $2^{32}$ and a 32-bit prime is not important, but a compiler translation from i32 to mod p isn't technically "correct" and we should probably think about how to expose this to the developer/frontend. I guess this is conceptually similar to truncation and/or deciding approximation precision (e.g. LUT size) which are also relevant to TFHE, but in the mod p/polynomial approximation case we get with BFV/BGV and CKKS, "bits of precision" might not be sufficient as a metric/language to communicate the behavior.

2. Cleartext (e.g. $\mathbb{F}_p$) -> Plaintext Encoding (e.g., $R_p = \mathbb{Z}_p[X] / X^N + 1$)

For RLWE, the plaintext space is a polynomial ring, and we're generally much more interested in encoding integers (at this point, usually implicitly already considered mod p?). There are lots of ways to do this, starting with the trivial solution of just setting the constant coefficient to your integer and all other coefficients to zero, to decomposing your integer and putting a digit into each coefficient, to various forms of CRT-based "packing" or "batching" that allows one to achieve SIMD-style semantics. By far the most common is "full" packing, but you can also trade off a lower number of "slots" for larger (i.e., $\mathbb{F}_{p^d}$ for $d > 1$) slots. CKKS has some extra complexity here as the message space is technically a vector of complex numbers but of course it's approximate and in fixed-(ish)-point representation, so basically just more SIMD integer vector stuff.

Question: What does TFHE use here? The first RLWE "plaintext" I think of in the context of TFHE is the blind rotation test vector, and that looks like a trivial (non-CRT) "packing" of a vector of integers (with lots of repetition) into the coefficients of the polynomial?

3. Plaintext (e.g., $R_p = \mathbb{Z}_p[X] / X^N + 1$) -> Ciphertext (e.g., $R_q = \mathbb{Z}_p[X] / X^N + 1$) Encoding

In descriptions of BFV/BGV, this step is usually mixed in with encryption, but I've also seen this referred to as "MSB/LSB encoding", referring to how message and noise are arranged: (Image from https://pqcrypto2023.umiacs.io/slides/2.2.pdf)

4. Representation

In addition to the above, we also need to consider how the polynomial itself is represented (e.g., coefficient-representation vs eval/NTT-form, RNS vs BigNum, etc) but that seems mostly orthogonal to the discussion above? In addition, most RLWE schemes actually don't juse use a single coefficient modulus but instead a "chain" (in RNS, the partial products of the RNS moduli usually make up the chain elements, in non-RNS, the chain could be built more freely but tends to be defined similarily). Note also, that the actual FHE scheme algorithms change depending on these representation choices (NTT stuff is pretty trivial, just iNTT if you need actual coefficients, but RNS versions are quite different and have different noise growth).

Situation in HEIR

Right now, we have the following attributes:

• lwe.bit_field_encoding which takes a start and width and describes where in a larger number of bits the "interesting" bits (i.e., message bits) are. This seems to be capturing Step 3, though I'm not sure how we'd express CKKS here? Maybe that's what lwe.unspecified_bit_field_encoding is for? Actually, I'm not even sure how to capture BFV/BGV with this, as they can (iirc) scale their noise or message by non-power-of-two numbers, so the "bits" idea breaks down a bit?

• lwe.polynomial_coefficient_encoding which also has the start/width parameters and basically seems to indicate the "trivial coefficient packing" as used in TFHE's blind rotate? (i.e., Step 2)? Similarily, we have lwe.polynomial_evaluation_encoding and lwe.inverse_canonical_embedding_encoding (which actually already has a TODO comment wondering about how bitfield would work here, see #183)

• polynomial.ring which encode things relevant to 4, but don't really give us a way to encode things such as as the modulus chain (which is needed independently of RNS).

And then we have the lwe.rlwe_ciphertext type which relies on the above attributes to describe the ciphertext.

---

Question: How can we best express the required information for an, e.g. BGV ciphertext, specifically moduli chains and/or RNS?

[j2kun]

I want to reply in more detail later, but to try to help clear up any initial confusion, I'm convinced now that the encoding attributes I originally defined for RLWE are plain wrong.

In general, I consider "encoding" to be any and all preparation of the application data before encryption that does not require key material or ciphertext-specific random samples. I was mistaken in where that line was drawn for BGV/BFV when originally writing that.

On Wed, Jul 10, 2024, 1:57 PM Alexander Viand @.***> wrote:

In order to avoid cluttering up the discussion of #762 https://github.com/google/heir/issues/762 (Enc/Dec and Randomness handling), I figured I'd create a new issue to (a) help myself get my thoughts straight on the various mappings/encodings and (b) get some feedback, especially with regards to the TFHE perspective on RLWE.

1. Application Data (e.g. i32) vs. "Cleartext" (e.g. $\mathbb{F}_p$) Semantics

Not sure if "Cleartext" is the right name here, but we usually have a disconnect between the semantics of the actual data type in the application (e.g., i32 or f32) and what we actually end up achieving under HE (usually finite field arithmetic with prime modulus). I know this isn't the case when we do bit-wise encryption (be it in TFHE or in BFV/BGV) but I'm not sure how 4-bit TFHE works here. Clearly, it's something to consider for "word-wise" FHE like BGV/BGV and especially CKKS, with its approximate nature.

Of course, for many applications, the difference between computation mod $2^{32}$ and a 32-bit prime is not important, but a compiler translation from i32 to mod p isn't technically "correct" and we should probably think about how to expose this to the developer/frontend. I guess this is conceptually similar to truncation and/or deciding approximation precision (e.g. LUT size) which are also relevant to TFHE, but in the mod p/polynomial approximation case we get with BFV/BGV and CKKS, "bits of precision" might not be sufficient as a metric/language to communicate the behavior.

2. Cleartext (e.g. $\mathbb{F}_p$) -> Plaintext Encoding (e.g., $R_p = \mathbb{Z}_p[X] / X^N + 1$)

For RLWE, the plaintext space is a polynomial ring, and we're generally much more interested in encoding integers (at this point, usually implicitly already considered mod p?). There are lots of ways to do this, starting with the trivial solution of just setting the constant coefficient to your integer and all other coefficients to zero, to decomposing your integer and putting a digit into each coefficient, to various forms of CRT-based "packing" or "batching" that allows one to achieve SIMD-style semantics. By far the most common is "full" packing, but you can also trade off a lower number of "slots" for larger (i.e., $\mathbb{F}_{p^d}$ for $d > 1$) slots. CKKS has some extra complexity here as the message space is technically a vector of complex numbers but of course it's approximate and in fixed-(ish)-point representation, so basically just more SIMD integer vector stuff.

Question: What does TFHE use here? The first RLWE "plaintext" I think of in the context of TFHE is the blind rotation test vector, and that looks like a trivial (non-CRT) "packing" of a vector of integers (with lots of repetition) into the coefficients of the polynomial?

3. Plaintext (e.g., $R_p = \mathbb{Z}_p[X] / X^N + 1$) -> Ciphertext (e.g., $R_q = \mathbb{Z}_p[X] / X^N + 1$) Encoding

In descriptions of BFV/BGV, this step is usually mixed in with encryption, but I've also seen this referred to as "MSB/LSB encoding", referring to how message and noise are arranged: image.png (view on web) https://github.com/google/heir/assets/88422715/12983074-150a-46a0-a0ae-59b5c1692321 (Image from https://pqcrypto2023.umiacs.io/slides/2.2.pdf)

4. Representation

In addition to the above, we also need to consider how the polynomial itself is represented (e.g., coefficient-representation vs eval/NTT-form, RNS vs BigNum, etc) but that seems mostly orthogonal to the discussion above? In addition, most RLWE schemes actually don't juse use a single coefficient modulus but instead a "chain" (in RNS, the partial products of the RNS moduli usually make up the chain elements, in non-RNS, the chain could be built more freely but tends to be defined similarily). Note also, that the actual FHE scheme algorithms change depending on these representation choices (NTT stuff is pretty trivial, just iNTT if you need actual coefficients, but RNS versions are quite different and have different noise growth). Situation in HEIR

Right now, we have the following attributes:

-

lwe.bit_field_encoding which takes a start and width and describes where in a larger number of bits the "interesting" bits (i.e., message bits) are. This seems to be capturing Step 3, though I'm not sure how we'd express CKKS here? Maybe that's what lwe.unspecified_bit_field_encoding is for? Actually, I'm not even sure how to capture BFV/BGV with this, as they can (iirc) scale their noise or message by non-power-of-two numbers, so the "bits" idea breaks down a bit?

lwe.polynomial_coefficient_encoding which also has the start/width parameters and basically seems to indicate the "trivial coefficient packing" as used in TFHE's blind rotate? (i.e., Step 2)? Similarily, we have lwe.polynomial_evaluation_encoding and lwe.inverse_canonical_embedding_encoding (which actually already has a TODO comment wondering about how bitfield would work here, see #183 https://github.com/google/heir/issues/183)

polynomial.ring which encode things relevant to 4, but don't really give us a way to encode things such as as the modulus chain (which is needed independently of RNS).

And then we have the lwe.rlwe_ciphertext type which relies on the above attributes to describe the ciphertext.

Question: How can we best express the required information for an, e.g. BGV ciphertext, specifically moduli chains and/or RNS?

— Reply to this email directly, view it on GitHub https://github.com/google/heir/issues/785, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAS2PKW2JJSEY6NLUPMQSA3ZLWN2FAVCNFSM6AAAAABKVVMILSVHI2DSMVQWIX3LMV43ASLTON2WKOZSGQYDCNZRGU2DAMA . You are receiving this because you are subscribed to this thread.Message ID: @.***>

[AlexanderViand-Intel]

Let me also add a list of information I think we need from a BGV/BFV ciphertext (assuming we follow Kim et al. and do a unified implementation) for the bgv->lwe/poly lowering:

• MSB or LSB (3)? - required to know what lowering to use for mul/relin and modswitch. not required if we don't do unified BFV/BGV
• RNS or BigNum (4)? - required to choose which lowering to use for modswitch/relin, as the math changes a bit
• Modulus Chain (4) - required to generate the constants/metadata for modswitch/relin. Note that we need both the current modulus chain (i.e., what's left) AND the full original modulus chain (e.g., for relin with modulus extension, where we actually mod switch UP to a larger modulus)

Later on (either lwe->poly or --convert-polnomial-mul-to-ntt), we'll also need the current polynomial ring, in order to generate the metadata for the NTT/iNTT. This would also (I think?) be the right point to add montgomery representation?

The other steps (1/2) seem mostly important for the secret -> fhe scheme step, where they're necessary decide what schemes are applicable and when/how to do noise management.

[AlexanderViand-Intel]

I've played around a bit with this now, and come up with the following design proposal:

The lwe.rlwe_ciphertext no longer has a single lwe.rlwe_params attribute, but instead a series of (default/optional) attributes:

• dimension (C++ unsigned int) - default value = 2, same as dimension from lwe.rlwe_params.

• Key Information, probably encapsulated in some attribute, rather than as individual elements:

  • key (type TBD) - an identifier for the (base, i.e., just $s$) secret key used to encrypt this ciphertext. Important for multi-key HE. Should default to some kind of "dummy" value that indicates "implicit sk in a situation with only one sk"
  • key_basis? (ArrayRef<int64_t>?) - as in the bgv.relinearize op. Maybe not necesary, unless there are situations where dimension doesn't uniquely determine a key_basis

• Plaintext Encoding Information (?) (as in Step 2 above).
  Probably an "Enum" (not sure how that'd be modelled in TableGen) of (fixed/updated) attributes like:

  • lwe.constant_coefficient_encoding - puts a single integer into the constant coefficient, all others zero. This works and supports homomorphic add/mul but is incredibly wasteful. Rotation isn't really meaningful for this representation.
  • lwe.trivial_coefficient_packing - basically the TFHE approach of just interpreting a list of integers as the coefficients. This doesn't support homomorphic multiplication afaik, as we'd get weird cross products. Rotations by $k$ are possible by multiplying with $X^k$. IIRC, with the right choice of ideal, this can be as simple as rotating the coefficients?
  • lwe.digitwise_coefficient_packing - decomposes a single integer into digits and inteprets those as coefficients. This actually allows limited homomorphic multiplication, but great care must be taken to avoid digits overflowing. Rotations with $X^k$ correspond to "r/lshifts" of the integer. I suggest not to worry about supporting this for the moment.
  • lwe.crt_packing - maps a vector of integers in $\mathbb{F}_{p^d}$ into a single polynomial in $R_p = \mathbb{Z}_p[X] / X^N + 1$ using the Chinese Remainder Theorem. This allows full SIMD-style homomorphic operations and rotations via galois automorphisms (computed as a permutation of coefficients followed by a keyswitch from the permuted key to the old key, iirc). We might want to differntiate betweren the common "full" packing ($d = 1$) and "advanced" packings with $d > 1$. As OpenFHE doesn't support the latter (afaik), we probably don't need to support this for now, either.
  • lwe.inverse_canonical_embedding_encoding - CKKS's "fancy" packing, behaves mostly like "full CRT packing". Might already have the "scale" we need to keep track of, or that might be added during encryption only (need to look this up again).

  EDIT: I'm actually not sure we still need this information attached to the ciphertext. After all, this is mostly important information when translating from secret to a specific scheme, which happens in previous passes (e.g. mlir-to-bgv). Instead, this attribute might only need to be attached to the lwe.encode/decode operations (rather than any types) by those passes.

• Encryption Information (as in Step 3 above). Probably necessary if we want unified ciphertxt types for BGV/BFV/CKKS. This could be as simple as an enum of lwe.msb_enc / lwe.lsb_enc / lwe.mix_enc (for CKKS) if we're just using it to indicate which lowering to choose, but a single combined attribute that actuall includes the constant by which things are scaled could be useful for things such as noise management passes or even just as a place for modswitch lowerings to get the required constants from.

  • Mod Switch Information (Optional). In schemes that support mod_switch, we really have two ciphertext spaces to worry about:
    • the "full" ring this could refer to either what eval keys are encrypted into, or what fresh ciphertexts are encrypted into - which aren't always the same. For the relin lowering we need the first, so I'd suggest using that definition.
  • the "current" ring - the ring the ciphertext actually exists in at the moment.

  However, we don't actually need the "ring" (in the polynomial.ring sense) here for the lowerings, instead we need the (full and current) modulus chain, and frequently some additional info (scale in CKKS, noise estimate in some variants of BGV), so it'd be (an attribute wrapping) full_chain, current_chain and scale (or similar).

• Polynomial "Ring" Information (Might also include Representation Information, as in Step 4) above?): Clearly, we need some information on how to eventually lower the ciphertext to polynomials. However, it does not seem like a simple polynomial.ring attribute is sufficient for that, as it doesn't really allow us to capture RNS/etc. This can probably be solved relatively simply by introducing an RNSAttr (similar to RNSType) and allowing either an RNSAttr<RingAttr> or a RingAttr. However, this would break a bunch of existing code that assumes that there's, e.g., a single coefficient modulus. Maybe we need to fix/update that code anyway to support modswitch-based schemes, or maybe we can add some kind of interface/helper function that computes the total modulus from the RNS elements.

  I don't think we actually need NTT/montgomery/etc information at the ctxt level, as we can hopefully delay that until later lowerings. However, RNS does matter at the scheme/LWE level, as it influences HE algorithms in non-trivial ways (i.e., there's no automated way to transform a non-RNS HE scheme to one that works over RNS)

---

Alternativel/in addition to rlwe_ciphertext, we could also define a glwe_ciphertext that can express any kind of GLWE ciphertext, including LWE and RLWE ciphertexts. This would have most of the attributes from above, but also

• shape (type TBD[^1]) as a replacement and generalization of dimension
• Make the "ring" information optional.
• Any other LWE-specific attributes, though I guess most are already expressible with the set above (e.g., extending the encoding enum with LWE-specific encodings)

[^1]: Tensor uses a pretty complex system with some kind of Shape_ShapeType, but there's also "ArrayRef<int64_t>":$shape used by memrefs which might be

[j2kun]

So I haven't had time to really process all of the above and make concrete suggestions, but I will say that, in my opinion, (1) and (2) in https://github.com/google/heir/issues/785#issue-2401715400 are both "encoding" and (3) and (4) are not. In particular key information is not part of encoding.

Encoding is just "how do you make your application data suitable to be encrypted" and everything else about the cryptosystem is encryption. As such, I think the current RLWEPlaintext type has everything it needs: the ring (plaintext space), the encoding method (includes packing method, RNS choices, coefficient/NTT domain), and the underlying type.

Nb., the underlying type can be a single scalar value, if the encoding method splits that into digits and packs the digits. Or it could be a tensor of small scalars, if those are directly packed.

The ciphertext should have all the same data, along with anything else needed to use the scheme (moduli chain, "MSB/LSB" scaling factors (I don't want to call this encoding), mod switch info, etc. And I imagine they would all be optional attributes since the specific schemes can use them or not depending on the variants. We might do ourselves a favor by augmenting this with some helper methods that tie the variants to specific checks on the attributes (e.g., satisfiesPaperXYZ2021 which checks for the existence of three attributes and appropriate values for them), and we can use those as guards for various lowerings.

[j2kun]

@AlexanderViand-Intel I suspect there is a particular part of this encoding business that is the most uncertain. Can you decide on which and we can iron that out first? Is it the RNS/BigNum stuff?

[AlexanderViand-Intel]

@AlexanderViand-Intel I suspect there is a particular part of this encoding business that is the most uncertain. Can you decide on which and we can iron that out first? Is it the RNS/BigNum stuff?

I think most of this was just from naming/terminology confusion, it now seems relatively straightforward to separate.

I will say that, in my opinion, (1) and (2) in #785 (comment) are both "encoding" and (3) and (4) are not. In particular key information is not part of encoding.

Encoding is just "how do you make your application data suitable to be encrypted" and everything else about the cryptosystem is encryption.

I think I agree with this clasification~ Any suggestions for an alternative name for (3) and (4)?

[asraa]

https://gist.github.com/asraa/6105c144aa10295aa4f021438d5b046d

I started a small scratch doc that I'll convert into a draft PR for commenting purposes..

BTW:

Maybe not necesary, unless there are situations where dimension doesn't uniquely determine a key_basis

yes! a galois rotation doesn't change the dimension but changes the key basis into something like (1, s^i) where it's a rotation by i.

I'm suggesting encryption info attributes for (3) - to me this stuff is relevant to the encryption process / step (computing how to place the Z_p plaintext into the Z_q ciphertext during encryption).

[j2kun]

+1, the only murky part is the parameters that are not specific to encryption per se, but to the overall homomorphicness/performance of the cryptosystem. But I think "EncryptionParams" or similar is sufficient.