Help regarding FHE.Mult(ct_1, ct_2)

[aaallami]

Hi everyone, Could you please help me understand how the multiplication has been done in the Seal library? Based on the BFV paper, the multiplication causes the ciphertext to be quadratic. In other words, Mult(ct1(c_0, c_1), ct2(c_0, c_1)) will produce three components rather than two (c_0, c_1, c_2). To rectify this problem, the BFV paper uses the relinearization technique and offers two methodes to get that done. Therefore, my questions are as follows: 1- Which relinerizarion techinque is implemented in the Seal? 2- As far as I remember Seal allows multiplying two ciphertexts without relinearization which produces the right result when is decrypted. So the question, how were you guys able to correct the increase in the ciphertext components without every need to relinearize it in this case? 3- Is there a way to calculate the tight noise budget for L levels? Thanks

[fionser]

1. The concrete version of the relineraization of SEAL is not documented. In fact, it uses JC Bajard et al.'s full RNS (see paper ), with the special prime technique introduced in HElib, and Shai Halevi et al.'s trick for saving some constant multiplications. (see another paper)
2. For your question, I think the relinearization is inevitable. For ciphertexts with more than 3 components, we need a relin key of a higher degree to switch back to two-component ciphertext. By default, SEAL generates relin-key for three component ciphertexts. To generate a higher degree of relin-key see this API.

[WeiDaiWD]

Thanks, @fionser .

To generate a higher degree of relin-key see this API.

To reduce the number of components in a ciphertext, you need to perform relinearization with the these non-default keys.

how were you guys able to correct the increase in the ciphertext components without every need to relinearize it in this case?

SEAL can decrypt a ciphertext that has more than 2 components. The decryption works like multiplying the i-th component of a ciphertext with the i-th power of the secret key and summing up all products, i.e., an inner-product <(c0,c1,...,cl), (1,s,s^2,...,s^l)>. SEAL's Decryptor will detect that there are more than 2 components in the ciphertext and generate enough powers of secret key automatically. This method is convenient but more noisy compared to performing relinearization.

Is there a way to calculate the tight noise budget for L levels?

It's hard to calculate an accurate noise budget. However, you can estimate an upper-bound of it. The method in this paper gives the tightest bound so far. Or you may call Decryptor::invariant_noise_budget on a ciphertext (even if it has more than 2 components).

[aaallami]

@fionser, I appreciate your feedback. Thanks, @WeiDaiWD. I think using <(c0,c1,...,cl), (1,s,s^2,...,s^l)> you are referring to the relinearstion version1 reported by the original FV paper on page 8. It takes a ciphertext of three components and produces two componets which then can be decryped. If that's not the case could you please attach the paper that explains the method you mentioned to decrypt a ciphertext of three components. Thanks

[WeiDaiWD]

SEAL (Evaluator::relinearize*) uses relinearization version 2 when poly_modulus_degree >= 4096 and uses version 1 if poly_modulus_degree <= 2048. Both versions are implemented with respect to the RNS form.

<(c0,c1,...,cl), (1,s,s^2,...,s^l)> is not relinearization. This is how a multi-component ciphertext is decrypted, end of page 7 of the paper.

[aaallami]

@WeiDaiWD great, I see your point. another question, I guess multiplying a plaintext with a ciphertext is not going to cause this problem and we do not need to do relinearization. I hope that's the case. Please, correct me if I am wrong as I couldn't find this case on the paper. Thanks

[WeiDaiWD]

I guess multiplying a plaintext with a ciphertext is not going to cause this problem and we do not need to do relinearization

That's right!

[aaallami]

@WeiDaiWD Many thanks to you