In the BGV paper [1], the authors say in §5.4 that you can have $\mathbb{Z}_p$ as plaintext size with a large $p$.

What is the impact of the size of $p$ on the ciphertext size and computational work of the cipher's algorithms?

I would need this to decide how big my plaintext space can be before it becomes impractical.


[1] Brakerski, Zvika, Craig Gentry, and Vinod Vaikuntanathan. “(Leveled) Fully Homomorphic Encryption Without Bootstrapping.” In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, 309–25. ITCS ’12. New York, NY, USA: ACM, 2012. doi:10.1145/2090236.2090262. http://eprint.iacr.org/2011/277

  • $\begingroup$ The bigger the modulo the more computationally expensive the modular operations. This is obvious. $\endgroup$
    – curious
    Jul 30, 2015 at 9:24
  • $\begingroup$ This is obvious indeed, so what I need is a quantitative answer, performances as a function of $p$, for instance with a big-O notation. $\endgroup$ Jul 30, 2015 at 9:49
  • $\begingroup$ You have to be more precise with respect to what operations you need to perform. For instance for multiplication there are various techniques:Karatsuba, Montgomery. Here you can find an idea : en.wikipedia.org/wiki/… $\endgroup$
    – curious
    Jul 30, 2015 at 10:37
  • $\begingroup$ My primary focus is ciphertext length; as to computational cost it is mainly the one of setup, keygen, encrypt and decrypt. Operations will be mainly sums which are very cheap with BGV. $\endgroup$ Jul 30, 2015 at 10:56
  • $\begingroup$ I think it is not clear in your mind. Ciphertext size depends on the size on the group and its bitstring representation which depends on $p$ obviously. What is your question about?size of p=1024bit which is the ciphertext space then |ciphertext|=1024 bits. Since you want additions why you need BGV, and not Paillier? $\endgroup$
    – curious
    Jul 30, 2015 at 12:29

1 Answer 1


A helpful resource to assess which ring-based FHE scheme (like BGV) would work best for you, see here: https://eprint.iacr.org/2015/889

In this paper they compare four schemes: BGV, FV, NTRU, and YASHE.

The reason I point you there is that one major factor in the performance of these schemes is the value of p. If a large p is used, BGV outperforms the rest. If a small p is used, YASHE wins, but not by too much. The other main factor is the L parameter.

The metric they use to compare them is the ciphertext size, which is crude but gives a rough estimate as to the computational time needed.


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.