Criptosistemul LWE este doar securizat CPA, așa cum se precizează, de exemplu, în Un deceniu de criptografie bazată pe zăbrele. Luați în considerare următorul sistem descris acolo (Secțiunea 5.2)
- Cheia secretă este un secret LWE uniform $s \in \mathbb{Z}_q^n$, iar cheia publică este unele $m \aprox (n+1) \log(q)$ mostre $(\bar{a}_i, b_i = \left <\bar{a}_i, s \right > +e$ colectate ca coloanele unei matrice $A$
$$A = \begin{pmatrix} \bar{A} \ b^t \end{pmatrix} \in \mathbb{Z}_q^{(n+1) \times m}$$
Unde $b^t = s^t \bar{A} +e e^t \mod q$.
- Pentru a cripta un pic $\mu \in \mathbb{Z}_2 = \{0,1\}$ folosind cheia publică $A$, se alege un unifrom $x \în {0,1}^m$ și scoate textul cifrat
$$c = A \cdot x + (0, \mu \cdot \lfloor \frac{q}{2} \rceil) \in \mathbb{Z}_q^{n+1}$$
- Pentru a decripta folosind cheia secretă $\mathbb{s}$, se calculează:
$$(-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}$$
$$\aproximativ \mu \cdot \lfloor \frac{q}{2} \rceil \in \mathbb{Z}_q^{n+1} \mod q$$
și testează dacă este mai aproape de $0$ sau $\frac{q}{2} \mod q$.
Lucrarea afirmă că „observăm că sistemul poate fi spart în mod trivial sub un atac activ sau cu text cifrat ales”.
Cum ar arăta un astfel de atac? Aș lua în considerare să criptez $0$ bit cu $x$ fiind totul $1$-s vector de preluat $e$ și apoi recuperați $s$ prin intermediul $\bar{A}^{-1} \cdot (b-e)$. Se cunosc alte moduri? Și există modalități cunoscute de a extinde aceste atacuri la versiunea securizată CPA a candidaților finaliști NIST-pqc, de exemplu, Kyber?
