Hệ thống mật mã LWE chỉ bảo mật CPA như ví dụ đã nêu trong Một thập kỷ của mật mã dựa trên lưới. Hãy xem xét hệ thống sau được mô tả ở đó (Phần 5.2)
- Khóa bí mật là bí mật LWE thống nhất $s \in \mathbb{Z}_q^n$, và khóa công khai là một số $m \approx (n+1) \log(q)$ mẫu $(\bar{a}_i, b_i = \left <\bar{a}_i, s \right > +e$ được thu thập dưới dạng các cột của ma trận $A$
$$A = \begin{pmatrix} \bar{A} \ b^t \end{pmatrix} \in \mathbb{Z}_q^{(n+1) \times m}$$
ở đâu $b^t = s^t \bar{A} +e e^t \mod q$.
- Để mã hóa một chút $\mu \in \mathbb{Z}_2 = \{0,1\}$ sử dụng khóa công khai $A$, một người chọn một unifrom $x \in {0,1}^m$ và xuất bản mã
$$c = A \cdot x + (0, \mu \cdot \lfloor \frac{q}{2} \rceil) \in \mathbb{Z}_q^{n+1}$$
- Để giải mã bằng khóa bí mật $\mathbb{s}$, người ta tính:
$$(-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$$
và kiểm tra xem nó có gần hơn với $0$ hoặc $\frac{q}{2} \mod q$.
Bài báo nói rằng "chúng tôi lưu ý rằng hệ thống có thể bị phá vỡ một cách tầm thường dưới một cuộc tấn công chủ động hoặc bản mã được chọn".
Một cuộc tấn công như vậy sẽ trông như thế nào? Tôi sẽ xem xét để mã hóa $0$ chút với $x$ là tất cả $1$-s vector để truy xuất $e$ và sau đó lấy $s$ qua $\bar{A}^{-1} \cdot (b-e)$. Có bất kỳ cách nào khác được biết đến? Và có cách nào để mở rộng các cuộc tấn công này sang phiên bản bảo mật CPA của các ứng cử viên lọt vào vòng chung kết NIST-pqc, chẳng hạn như Kyber không?
