Homomorphic Encryption and Semantic Security using Lattices?

Question

I've been reading Brakerski and Vaikuntanathan's "Efficient Fully Homomorphic Encryption from (Standard) LWE" and I'm still digesting pieces at a time.

Under section 1.1, "Re-Linearization: Somewhat Homomorphic Encryption without Ideals", they state they mask the plain text with noise. The noise is created with multiplications and additions of the plain text, and the result is cipher text:

To encrypt a bit $m$ in $\{0, 1\}$ using secret key $\mathbf{s}$ in $\mathbb{Z}_q^n$, we choose a random vector $\mathbf{a}$ in $\mathbb{Z}_q^n$ and a "noise" e and output the cipher text

$c = (\mathbf{a},b = \langle \mathbf{a},\mathbf{s} \rangle + 2e + m)$

The key observation in decryption is that the two “masks” – namely, the secret mask $\langle \mathbf{a},\mathbf{s} \rangle$ and the "even mask" $2e$ – do not interfere with each other. That is, one can decrypt this cipher text by annihilating the two masks, one after the other: The decryption algorithm first re-computes the mask $\langle \mathbf{a},\mathbf{s} \rangle$ and subtracts it from $b$, resulting in $2e + m \pmod{q}$. Since $e \ll q$, then $2e + m \pmod{q} = 2e + m$.

How can this be semantically secure if the same mask $\langle \mathbf{a},\mathbf{s} \rangle$ is being used on messages? That is, two different encryptions of the same value (say "10") would produce the same cipher texts.

If I added two numbers (say "10" and "100"), wouldn't they need to be masked with the same $\langle \mathbf{a},\mathbf{s} \rangle$?
Or does this scheme require additional accounting somewhere to allow for different $\langle \mathbf{a},\mathbf{s} \rangle$ masks?

Answer 1

The LWE assumption

I think we should start from the LWE assumption. Let $n$ and $q$ be integers and let $\chi$ be a distribution over $\mathbb{Z}_q$. We often take $\chi$ as a Gaussian with small variance. (We take an error $e$ from this distribution $\chi$ and assume that $|e| \ll q$.)

The LWE assumption states that any efficient adversary cannot distinguish two oracles if a vector $\mathbf{s} \in \mathbb{Z}_q^n$ is chosen uniformly at random;

• one is the random oracle that returns $(\mathbf{a},b) \in \mathbb{Z}_q^n \times \mathbb{Z}_q$ chosen uniformly at random
• the other is the LWE oracle that returns $(\mathbf{a},b) \in \mathbb{Z}_q^n \times \mathbb{Z}_q$, where $\mathbf{a} \gets \mathbb{Z}_q^n$, $e \gets \chi$, and $b = \langle \mathbf{a},\mathbf{s} \rangle + 2e$. (Note: I replace $e$ with $2e$ from the correct definition. This is a minor problem.)

The LWE-based Symmetric-key Encryption

Keeping the assumption in mind, we next review the symmetric-key encryption scheme appeared in your quotation.

• $\mathsf{Gen}(n,q)$: Choose $\mathbf{s} \in \mathbb{Z}_q^n$ uniformly at random. The secret key is $\mathbf{s}$.
• $\mathsf{Enc}(\mathbf{s},m \in \{0,1\})$:
  • Choose $\mathbf{a} \in \mathbb{Z}_q^n$ uniformly at random.
  • Take a sample $e$ from $\chi$.
  • Compute $b = \langle \mathbf{a},\mathbf{s} \rangle + 2e + m \in \mathbb{Z}_q$.
  • Output a ciphertext $c = (\mathbf{a},b)$.

This encryption scheme is apparently IND-CPA. In the IND-CPA game, denoted by $G$, the adversary has an encryption oracle which has a secret key $\mathbf{s}$. Let us replace the encryption oracle with the random oracle and call this game as $G'$. It is easy to show that $G$ and $G'$ are indistinguishable under the LWE assumption.

Answer

How can this be semantically secure if the same mask $\langle \mathbf{a},\mathbf{s} \rangle$ is being used on messages? That is, two different encryptions of the same value (say "10") would produce the same cipher texts. If I added two numbers (say "10" and "100"), wouldn't they need to be masked with the same $\langle \mathbf{a},\mathbf{s} \rangle$? Or does this scheme require additional accounting somewhere to allow for different $\langle \mathbf{a},\mathbf{s} \rangle$ masks?

By this definition, two ciphertexts $c_1, c_2$ of plaintexts $m_1, m_2 \in \{0,1\}$ under the secret key $\mathbf{s}$ are written as

• $c_1 = (\mathbf{a}_1, b_1) = (\mathbf{a}_1,\langle \mathbf{a}_1,\mathbf{s} \rangle + 2e_1 + m_1)$ and
• $c_2 = (\mathbf{a}_2, b_2) = (\mathbf{a}_2, \langle \mathbf{a}_2,\mathbf{s} \rangle + 2e_2 + m_2)$.

If we can obtain two ciphertexts with the same mask, that is, two ciphertexts with the same randomness $\mathbf{a}$, they are not IND-CPA secure. We have

• $c_1 = (\mathbf{a}, b_1) = (\mathbf{a},\langle \mathbf{a},\mathbf{s} \rangle + 2e_1 + m_1)$ and
• $c_2 = (\mathbf{a}, b_2) = (\mathbf{a}, \langle \mathbf{a},\mathbf{s} \rangle + 2e_2 + m_2)$.

It is easy to check the relation $m_1 - m_2 \bmod{2}$ by the relation $b_1 - b_2 \equiv 2e_1 + m_1 - (2e_2 + m_2) \bmod{q}$. Since $e_1, e_2, m_1, m_2$ is "small", $b_1 - b_2 \bmod{q} = 2(e_1 - e_2) + m_1 - m_2 \in [-q/2,q/2]$. Therefore, the difference $b_1 - b_2 \bmod{q}$ reveals the relation $m_1 - m_2 \bmod{2}$.

Finally, I mention that the scheme is additively homomorphic. Suppose that we have two ciphertexts

• $c_1 = (\mathbf{a}_1, b_1) = (\mathbf{a}_1,\langle \mathbf{a}_1,\mathbf{s} \rangle + 2e_1 + m_1)$
• $c_2 = (\mathbf{a}_2, b_2) = (\mathbf{a}_2, \langle \mathbf{a}_2,\mathbf{s} \rangle + 2e_2 + m_2)$.

Consider $c_1 + c_2 \in \mathbb{Z}_q^n \times \mathbb{Z}_q$.

$c_1 + c_2 = (\mathbf{a}',b')$ $ = (\mathbf{a}_1 + \mathbf{a}_2, \langle \mathbf{a}_1 + \mathbf{a}_2, \mathbf{s} \rangle + 2(e_1 + e_2 + (m_1 + m_2 \mathbin{\mathrm{div}} 2)) + (m_1 + m_2 \bmod{2}))$.

Multiplication is tricky. I recommend to read the BGV paper, which employs "tensor" to make notation simpler than the BV paper.