# What consequences do the plaintext space size has on the performances in the BGV scheme?

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.

## References

[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

• The bigger the modulo the more computationally expensive the modular operations. This is obvious. – curious Jul 30 '15 at 9:24
• 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. – Cédric Van Rompay Jul 30 '15 at 9:49
• 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/… – curious Jul 30 '15 at 10:37
• 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. – Cédric Van Rompay Jul 30 '15 at 10:56
• 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? – curious Jul 30 '15 at 12:29

## 1 Answer

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.