# Homomorphic Encryption and Semantic Security using Lattices?

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?

-
Is there a reason you chose that specific FHE cipher? I believe the standard LWE ciphers are much less efficient compared to the ring LWE ciphers. –  mikeazo Nov 27 '13 at 22:47
In the abstract description of the scheme (which I assume you are referring to) the vector $\bf s$ is the secret key and the vector $\bf a$ is randomly chosen for $every$ encryption. If you look at the definition of the homomorphic addition (multiplication) you see that they use ciphertexts with respect to independently chosen $\bf a$ and $\bf a'$ for encryption of message $m$ and $m'$. –  DrLecter Nov 28 '13 at 10:32
The secret is $\bf s$ and they descibe a secret key variant (as far as I can see that) –  DrLecter Nov 28 '13 at 11:39
@noloader the BGV system is probably the most popular one and has a few optimizations (1 and 2) plus an implementation. –  mikeazo Nov 28 '13 at 12:53
@curious $e$ is the error part of learning with errors. There are some good tutorials out there on the LWE problem that might help. $a$ is like the random values used in Paillier or ElGamal. Those random values are not part of the secret key. –  mikeazo Nov 28 '13 at 13:03

# 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.

-
Thanks xagawa. Sorry about the late accept on the answer. –  jww Dec 9 '13 at 6:11