LWE-криптосистема защищена только CPA, как, например, указано в Десятилетие криптографии на основе решеток. Рассмотрим следующую систему, описанную там (раздел 5.2)
- Секретный ключ представляет собой универсальный секрет LWE. $s \in \mathbb{Z}_q^n$, а открытый ключ какой-то $m \приблизительно (n+1) \log(q)$ образцы $(\bar{a}_i, b_i = \left <\bar{a}_i, s \right > +e$ собраны как столбцы матрицы $А$
$$A = \begin{pmatrix} \bar{A} \ b^t \end{pmatrix} \in \mathbb{Z}_q^{(n+1) \times m}$$
куда $b^t = s^t \bar{A} +e e^t \mod q$.
- Чтобы немного зашифровать $\mu \in \mathbb{Z}_2 = \{0,1\}$ с помощью открытого ключа $А$, выбирается униформа $x \in {0,1}^m$ и выводит зашифрованный текст
$$c = A \cdot x + (0, \mu \cdot \lfloor \frac{q}{2} \rceil) \in \mathbb{Z}_q^{n+1}$$
- Чтобы расшифровать с помощью секретного ключа $\mathbb{s}$, вычисляется:
$$(-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}$$
$$\приблизительно \mu \cdot \lfloor \frac{q}{2} \rceil \in \mathbb{Z}_q^{n+1} \mod q$$
и проверяет, ближе ли он к $0$ или же $\frac{q}{2} \mod q$.
В документе говорится, что «мы отмечаем, что система тривиально взломана при активной атаке или атаке с выбранным зашифрованным текстом».
Как будет выглядеть такая атака? Я бы подумал о шифровании $0$ немного с $х$ быть всем $1$-s вектор для получения $е$ а затем получить $s$ с помощью $\bar{A}^{-1} \cdot (b-e)$. Известны ли другие способы? И известны ли способы распространить эти атаки на CPA-защищенную версию кандидатов в финалисты NIST-pqc, например, Kyber?
