search

microsoft / SEAL

Microsoft SEAL is an easy-to-use and powerful homomorphic encryption library.
https://www.microsoft.com/en-us/research/group/cryptography-research/
MIT License
3.55k stars 706 forks source link

BGV noise budget #586

Open imadchabounia opened 1 year ago

imadchabounia commented 1 year ago

Hello,

In SEAL the function invariant_noise_budget is supported for both BFV and BVG, but for BGV I just want to know if an analogous of invariant_noise_budget is used ? also I got the same noise budget for freshly encrypted ciphertexts for both schemes under the same parameters configuration, is that expected ? can I have a brief explanation of that ? because I think it is unexpected for the noise budget to be the same since noise behavior of the schemes is bit different during evaluation

Thanks,

Pro7ech commented 1 year ago

That's because the two schemes are fundamentally identical, they only differ by their encoding and tensoring operation. So until you do a multiplication, the noise budget between the two schemes will remain the same.

imadchabounia commented 1 year ago

Yes I agree that both schemes are fundamentally identical, but I want to confirm if the noise budget for both schemes is computed in the same way. in BFV invariant noise budget of a given ciphertext ct is defined by -log(2 * norm(v)) and this assure correctness since the inequality that must be satisfied during dycryption which norm(v) < 1/2 , but in case of BGV I saw in a paper that the concept of invariant noise budget don't exist and thus they suggested an analogous defined by log(q) - log(norm(v)) -1 https://eprint.iacr.org/2019/493.pdf and likewise this definition assure correctness since the bound for BGV is norm(v) <= q/2 .. so this is the main reason for which I was wondering how things are defined in SEAL for BGV especially that we are getting the same noise budget for fresh ciphers.

please let me know about your thoughts

Pro7ech commented 1 year ago

The same method is used for both schemes: Decryptor::invariant_noise_budget: log(norm(dec(ct))) - log(norm(plaintext)) - 1 = log(norm(err)/2).

imadchabounia commented 1 year ago

actually the method you mentioned looks more promising for computing noise budget , but when I was looking at the code in Decryptor::invariant_noise_budget I couldn't figure out where plaintext is used, what I understood is that noise_poly is computed as dot product of ciphertext and secret key s then in case of BGV it is used directly whereas in BFV the polynomial is multiplied by plain_modulus because of scaling factor delta .. the final value computed is equal to log(q)-log(norm(noise_poly))-1 . in overall I can see that they are computed in the same way with a slight adaptation in case of BFV.