solution

Bài toán Học với lỗi (Learning With Errors — LWE) là nền tảng của nhiều chuẩn mật mã hậu lượng tử NIST (Kyber, Dilithium). Xét sơ đồ mã hoá khoá công khai thu nhỏ của Regev cho 1 bit mỗi lần.

Khoá công khai gồm ma trận $A \in \mathbb{Z}_q^{m \times n}$ (hàng $A_i$) và vector $b = (b_1, \dots, b_m)$ với $b_i \equiv \langle A_i, s \rangle + e_i \pmod q$ ($s$ là khoá bí mật, $e_i$ nhiễu nhỏ — cho trước trực tiếp trong đề, không cần tính lại).

Mã hoá bit $\mu \in \{0, 1\}$: chọn một tập con chỉ số $S \subseteq \{1, \dots, m\}$ (cho dưới dạng chuỗi bit độ dài $m$, ký tự 1 tại vị trí $i$ nghĩa là $i \in S$), tính

$a' = \sum_{i \in S} A_i \bmod q, \qquad b' = \Big(\sum_{i \in S} b_i + \mu \Big\lfloor \frac{q}{2} \Big\rfloor\Big) \bmod q$

Bản mã là $(a', b')$.

Giải mã bằng khoá bí mật $s$: tính $d = (b' - \langle a', s\rangle) \bmod q$, sau đó đưa $d$ về đại diện đối xứng $d_c \in (-q/2, q/2]$ (nếu $d > q/2$ thì $d_c = d - q$, ngược lại $d_c = d$). Bit giải mã được là $0$ nếu $|d_c| < q/4$, ngược lại là $1$.

Cho $A$, $b$, $s$ và $T$ truy vấn mã hoá/giải mã (mỗi truy vấn gồm $S$ và $\mu$), với mỗi truy vấn hãy thực hiện mã hoá rồi giải mã ngay và in ra bit thu được.

Ví dụ

Input:

3 32 4
27 2 2 22
7 1 17
15 14 8
6 5 27
2 1 5
3 5 2
4
1111 0
0000 1
1010 1
0101 0

Output:

0
1
1
0