0
$\begingroup$

For SIMD fully homomorphic encryption scheme like BFV/BGV, and the underlying R-LWE problem parameterized by $n, p, q, \alpha$ (respectively the dimension, the plaintext modulus, the ciphertext modulus and a parameter characterizing the distribution for the error), the choice of parameters is crucial for security. I have read this paper for choosing parameters, but I was wondering about the choice of $p$, as it is not explained: "the application will have to select a dimension n, and a ciphertext modulus q, (along with a plaintext modulus and a choice of encoding which are not discussed here)".

But from my understanding this choice is important both for security (e.g. the plaintext space has to be smaller than the ciphertext space) and to maintain FHE. In the paper introducing BGV, the ring $\mathcal R_2$ is used for the plaintext space, and it is briefly mentioned that a ring $\mathcal R_p$ could be used but with not much further details.

Could anyone please provide a source/explanation for the choice of $p$ and it's effect on the scheme? Also as a practical case, is it possible have a secure (e.g. 128 bits) BFV/BGV scheme for let's say $p\approx 2^{64}$, and still be able to do (homomorphic) addition, multiplication and bootstrapping?

Thank you.

$\endgroup$

1 Answer 1

0
$\begingroup$

Actually $p$ is not related to security, it's only related to usability: larger $p$ could hold larger plaintext at the cost of more error growth.

As you can see in the Homomorphic encryption standard (https://homomorphicencryption.org/), they only standardize $n$ and $q$. One can use any meaningful $p$ as long as they think the computation errors are tolerable.

$\endgroup$
1
  • $\begingroup$ I already understood that, and cited the paper published by Homomorphic Encryption Standardization. But as you say it yourself it leads to more noise growth, so it's choice still has to be considered for very large values to still allow let's say certain multiplicative depth. Also with your explanation I feel like $p$ could be as big as I want (even $p>>q$), which is from my understanding not the case. $\endgroup$ Commented May 10 at 8:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.