# How can CPA-secure LWE cryptosystem be broken by an active attacker?

The LWE-cryptosystem is only CPA-secure as for example stated in A Decade of Lattice-Based Cryptography. Consider the following system described there (Section 5.2)

• The secret key is a uniform LWE secret $$s \in \mathbb{Z}_q^n$$, and the public key is some $$m \approx (n+1) \log(q)$$ samples $$(\bar{a}_i, b_i = \left <\bar{a}_i, s \right > +e$$ collected as a the columns of a matrix $$A$$ $$A = \begin{pmatrix} \bar{A} \\ b^t \end{pmatrix} \in \mathbb{Z}_q^{(n+1) \times m}$$ where $$b^t = s^t \bar{A} +e e^t \mod q$$.
• To encrypt a bit $$\mu \in \mathbb{Z}_2 = \{0,1\}$$ using the public key $$A$$, one chooses a unifrom $$x \in {0,1}^m$$ and outputs the ciphertext $$c = A \cdot x + (0, \mu \cdot \lfloor \frac{q}{2} \rceil) \in \mathbb{Z}_q^{n+1}$$
• To decrypt using the secret key $$\mathbb{s}$$, one computes: $$(-s, 1)^t \cdot c = (-s, 1)^t \cdot A \cdot x +\mu \cdot \lfloor \frac{q}{2} \rceil) \in \mathbb{Z}_q^{n+1}$$ $$= e^t \cdot x + \mu \cdot \lfloor \frac{q}{2} \rceil) \in \mathbb{Z}_q^{n+1}$$ $$\approx \mu \cdot \lfloor \frac{q}{2} \rceil \in \mathbb{Z}_q^{n+1} \mod q$$ and tests whether it is closer to $$0$$ or $$\frac{q}{2} \mod q$$.

The paper states that "we note that the system is trivially breakable under an active, or chosen-ciphertext, attack".

How would such an attack look like? I would consider to encrypt the $$0$$ bit with $$x$$ being the all $$1$$-s vector to retrieve $$e$$ and then retrieve $$s$$ via $$\bar{A}^{-1} \cdot (b-e)$$. Are there any other ways known? And are there known ways to extend these attacks to CPA-secure version of the NIST-pqc finalist candidates, for example, Kyber?

Consider that adversary $$A$$ chooses two messages $$m_1 = 0$$ and $$m_2 = 1$$ as per Ind-CCA1 game and plays against the challanger.

• Adversary A sends $$m_1$$ and $$m_2$$ to the challenger.

• Challenger randomly choose $$b$$ between $$0$$ and $$1$$; $$b \stackrel{}{\leftarrow}$${0,1}

• Challenger calculates $$c:=Enc(s,m_b)$$ and send $$c$$ to $$A$$.

• Adversary performs additional operations in polynomial time, including calls to the encryption/decryption oracles, for ciphertexts different than $$c$$.

• $$c_0 = EncOracle(0)$$

• $$c' = c \oplus c_0$$

i.e. execute a homomorphic addition of $$m_b$$ with zero!.

• $$m' = DecOracle(c')$$

This is a valid request since $$c' \neq c$$.

• And we have $$m' = m_b$$

• if $$m' = 0$$ return $$0$$
else return $$1$$