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?
