Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [An toàn thông tin] Giải LWE khi biết s: khôi phục nhiễu e

    Khi đã biết khoá bí mật sss, ta có thể khôi phục vector nhiễu từ mẫu LWE (A,b)(A,b)(A,b):

    e=(b−A s) mod q.e = (b - A\,s) \bmod q.e=(b−As)modq.

    Vì nhiễu vốn nhỏ, ta biểu diễn nó ở dạng cân (centered) trong khoảng (−q/2,q/2](-q/2, q/2](−q/2,q/2]: nếu er>⌊q/2⌋e_r > \lfloor q/2\rfloorer​>⌊q/2⌋ thì thay er←er−qe_r \leftarrow e_r - qer​←er​−q.

    Ví dụ: q=7q=7q=7, nếu (b−As) mod 7=6(b-As)\bmod 7 = 6(b−As)mod7=6 thì dạng cân là 6−7=−16-7=-16−7=−1.

    • Định dạng đầu vào:

      Dòng 1: m n q. Tiếp theo m dòng ma trận A. Dòng kế: n số của s. Dòng cuối: m số của b.

    • Ràng buộc đầu vào:

      1≤m,n≤501 \le m,n \le 501≤m,n≤50; 2≤q≤1092 \le q \le 10^92≤q≤109.

    • Định dạng đầu ra:

      Một dòng gồm m số nguyên là vector nhiễu e ở dạng cân.

    Ví dụ:

    Đầu vào:

    2 2 7
1 2
3 4
1 1
3 1

    Đầu ra:

    0 1

    Giải thích:

    <A0,s>=3 ⇒ e0=(3−3) mod 7=0; <A1,s>=7 ⇒ e1=(1−7) mod 7=1.

    Đang tải editor...