bgv: Add a attribute to ciphertext to track plaintext bits

[asraa]

In the last HEIR meeting, we noted that rather than holding onto the underlying encrypted type, that it would be more useful to keep track of the number of plaintext bits that are encoded (potentially in each slot) of a BGV ciphertext. This would make the error analysis better. Likewise, at the BGV layer, it really is no longer relevant whether something was SIMD or not - this can occur at a higher level pass.

It may also be useful to have some notions of which slots are being used? Although not sure. That can be a separate issue.

[j2kun]

I think we could perhaps also migrate the bgv::Ciphertext type to the lwe dialect as an RLWE ciphertext type, which does not currently exist but we want to have it there.

[Maokami]

I'm uncertain, but it seems that the current encoding attributes, which track plaintext bits (e.g., lwe.BitFieldEncodingAttr, lwe.polynomial_evaluation_encoding, etc.), assume that the noise part of a ciphertext starts from the least significant bit (LSB). ( upto cleartext_start bit).

However, in the BGV scheme, it seems that the noise is located at the most significant bit (MSB) of the plaintext part, as illustrated in the following image:

Should we change the way of these modeling?

[asraa]

Should we change the way of these modeling?

Ah, I see the wording in https://github.com/google/heir/blob/main/include/Dialect/LWE/IR/LWEAttributes.td#L56-L58 implies the FV style with noise in the LSB. I don't think the attribute needs to change right now, since the attribute is only keeping track of the message bit position. The noise models specific to each scheme and the encryptions should specify / handle where the noise is added. I do think the wording should change to allow for both types.

[j2kun]

Agreed with Asra. I intended the current attribute to be generic enough to model both BFV and BGV (isn't it? For LSB, the messages start bits would be a small index), and if it's not we should make it so.

On Mon, Feb 12, 2024, 7:26 AM asraa @.***> wrote:

Should we change the way of these modeling?

Ah, I see the wording in https://github.com/google/heir/blob/main/include/Dialect/LWE/IR/LWEAttributes.td#L56-L58 implies the FV style with noise in the LSB. I don't think the attribute needs to change right now, since the attribute is only keeping track of the message bit position. The noise models specific to each scheme and the encryptions should specify / handle where the noise is added. I do think the wording should change to allow for both types.

— Reply to this email directly, view it on GitHub https://github.com/google/heir/issues/99#issuecomment-1938892134, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAS2PKSLILBRGNEWKEYYGBLYTIYCFAVCNFSM6AAAAAA3SZLPECVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMYTSMZYHA4TEMJTGQ . You are receiving this because you commented.Message ID: @.***>

[j2kun]

Taking a second look, yes I see how the docs are confusing. I think for BGV the interpretation of

#lwe_encoding = #lwe.bit_field_encoding<cleartext_start=4, cleartext_bitwidth=4>

Would be this: where n stands for noise and b for the message bits

       nn...n|bbbb
    MSB^         ^LSB

[j2kun]

This is fixed now since we moved BGV to use LWE types and attributes.