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?


1 Answer 1


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$

Adversary wins the game with an advantage 1.

In other words, the ciphertexts are malleable, there is no integrity to secure against CCA1 adversary.

  • $\begingroup$ Thanks! One question though: The attack laid out calls the decryption oracle after obtaining the challenge. However, the description of IND-CCA1 linked mentions that the attacker has to call the decryption oracle before obtaining the challenge: "That means: the adversary can encrypt or decrypt arbitrary messages before obtaining the challenge ciphertext." Would the attack laid out here not violate this requirement? $\endgroup$ Feb 3, 2022 at 11:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.