Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
Question 1: In which Somewhat Homomorphic Encryption schemes the plaintext space is defined over $\mathbb{F}_p$, where $p$ is a prime number.
It is said, in Somewhat homomorphic encryption the noise increases when homomorphic multiplication is used.
Question 2: Does this include multiplying a ciphertext by a plaintext? or just multiplying two ciphertexts?
Answer to question 1
I don't know about any somewhat (or leveled) homomorphic encryption whose plaintext space is the field $\mathbb{F}_p$.
Several schemes work over the ring $\mathbb{Z}_t[x] / \langle f(x) \rangle$, which is isomorphic to the field $\mathbb{F}_{p^n}$ when we chose $t$ to be a prime $p$ and $f(x)$ to have degree $n$. However, for security reasons, we usually are not able to chose $n = 1$.
Schemes based on integers usually have the field $\mathbb{Z}_2$ as the plaintext space and they do not seem difficult to adapt to an arbitrary prime instead of $2$.
Answer to question 2
Yes, multiplying a ciphertext by a plaintext increases the noise.
Ciphertexts in these noisy schemes are (roughly speaking) of the form $f(m) + e$, where $f$ is some function, $m$ is the message, and $e$ is the error. When we multiply a ciphertext $c = f(m) + e$ by another message, let's say $m'$, we end up with something like $f(m) \cdot m' + e\cdot m' = f(m \cdot m') + e'$, and this new error $e'$ is bigger than the original error $e$.
For instance, considerer the YASHE scheme:
As it is said on page 11 of SEAL's manual, for the FV scheme "plain multiplication increases the noise by a constant factor that depends on the plaintext multiplier".
And I am quite sure it also happens on plain multiplication of BGV scheme.
Answer for question 1:
According to this paper popular FHE schemes like BGV, NTRU and so on support plaintexts from a ring $R_p = Z_p[X]/\langle f(x) \rangle$ where $n = deg(f)$. The main trick is that the encryption noise should be a multiple of $p$ and the decryption is done by applying the reduction modulo $p$ instead of $2$.
Note: Although the plaintext space is a polynomial ring $R_p$ you can always encode your message $m$ as the free coefficient i.e. $m = x^0 \cdot m + x^1 \cdot 0 + \dots x^{n-1} \cdot 0$. One can argue that this is not really efficient because some coefficients are not used.
Fortunately there are some plaintext packing techniques (see Section 1.1) - a cool way to split the ring $R_p$ in sub-fields $F_p^d$ for which $d$ is a divisor of $n$ (this includes the case $d=1$).
You can view it as operating on contiguous sequences of length $d$ on an array of length $n$ and doing multiple encryptions at the same time.
Answer for question 2:
Additions and multiplications with public constants are (almost) for free in the FHE world, at least for BGV. Take for example the encryption from BGV scheme (page 12) instantiated with RLWE:
Consider $c \in R_q^{2}$ an encryption of $\textbf{m}_1 = (m_1, 0)\in R_q^{2}$. If we multiply the first component $c_1$ with a public constant $\textbf{m}_2 = (m_2, 0)$ and then decrypt using the secret key $s = (1, t_1)$ we get $m_1 \cdot m_2$.
Why? Use the fact that $b = Bt +2e$.
$c \cdot s = c_1 \cdot 1 + c_2 \cdot t = \\ m_1 \cdot m_2 + m_2 \cdot \sum_{i=1}^{N}b_ir_i - t \cdot \sum_{i=1}^{N}B_ir_i = \\ m_1 \cdot m_2 + m_2 \cdot r^t \cdot 2e $
Now if we reduce the last term mod $R_q$ and then mod $R_2$ we obtain $m_1 \cdot m_2$.
In this way we obtained $Enc(m_1 \cdot m_2)$ starting from $Enc(m_1)$, $m_2$ and added noise by a factor of $m_2$. This is better than encrypting $\textbf{m}_2$ and then do a homomorphic multiplication with a quadratic noise.
Bonus: Addition between $Enc(m_1)$ and $m_2$ can be done with zero noise!
