# Security of somewhat homomorphic encryption via LSB encoding?

I'm reading this paper https://eprint.iacr.org/2011/344.pdf

It says that "The secret-key encryption scheme whose security is based on the LWE assumption is rather straightforward. 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}^n_q$$ and a "noise" $$e$$ and output the ciphertext

$$c = (\mathbf{a}, b = \langle \mathbf{a}, \mathbf{s}\rangle + 2 e + m) \in \mathbb{Z}^n_q \times \mathbb{Z}_q$$

The key observation in decryption is that the two “masks” – namely, the secret mask〈a,s〉and the “even mask” 2e– do not interfere with each other. (* Footnote) "

The footnote says that "We remark that using $$2e$$ instead of $$e$$ as in the original formulation of LWE does not adversely impact security,so long as $$q$$ is odd (since in that case 2 is a unit in $$\mathbb{Z}_q$$)"

Does this mean using even $$q$$ incurs vulnerability of the scheme? If so, what is the intuition behind that?

• what is $2e$ in $\mathbb{F}_{2^n}$ – kelalaka Jan 12 at 20:26

## 1 Answer

As hinted by @kelalaka in the comments, note that $$q$$ is odd, and $$\gcd(2,q)=1.$$

Therefore within $$Z_q$$ we have that $$2e\neq 0,$$ if and only if $$e \neq 0,$$ so the noise is never masked.

• Does this mean that we cannot identify the $2e$ (and $m$) from given mod $q$ number? – user9414424 Jan 14 at 10:21