Hãy xem xét một công thức của LWE nơi chúng tôi được đưa ra một trong hai $(x,S x+e)$ hoặc $(x,u)$ --- ở đâu $S$ là một $m \times n$ ma trận bí mật/ẩn, $x$ là một mẫu ngẫu nhiên $n \times 1$ vectơ, $e$ là một $m \times 1$ Vectơ lỗi Gaussian và $u$ là một mẫu ngẫu nhiên thống nhất --- và được yêu cầu phân biệt giữa hai trường hợp này. Điều này sẽ khó đối với các thuật toán cổ điển, theo bài đăng đây. Gọi vấn đề này là "đảo ngược-LWE."
Tôi có một vài câu hỏi về cài đặt.
Vấn đề phân biệt có khó không $e$?
Lưu ý rằng trong LWE tiêu chuẩn, khi chúng tôi được cung cấp $(A,A s+e)$ hoặc $(x,u)$, và bảo phân biệt giữa 2 trường hợp thì đề dễ mà không bị lỗi. Chúng tôi chỉ giải một hệ phương trình tuyến tính để có được $n$ các mục của $s$.
Tuy nhiên, ở đây chúng ta cần tìm $m \times n$ mục của ma trận bí mật của chúng tôi $S$. Tôi không thấy làm thế nào để làm điều đó chỉ với $m$ phương trình.
Hãy xem xét một biến thể của vấn đề, trong đó chúng tôi được đưa ra một trong hai $$ \{ (x_1, Sx_1 + e_1), (x_2, Sx_2 + e_2), \ldots, (x_k, Sx_k + e_k)\} ~~\text{or}$$
$$\{ (x_1, u_1), (x_2, u_2), \ldots, (x_k, u_k)\},$$
và bảo phân biệt giữa hai trường hợp. Gọi vấn đề này là "LWE đảo ngược với một bí mật lặp đi lặp lại." $k$ là đa thức lớn trong $n$. Vấn đề này có khó không?
Lưu ý rằng một đối số kết hợp (như đối số được sử dụng trong một trong các câu trả lời đây) chỉ ra rằng vấn đề vẫn còn khó khăn. Đây là con lai $H_i$:
$$H_i = \{ (x_1, Sx_1 + e_1), (x_2, Sx_2 + e_2), \ldots, (x_i, Sx_i + e_i), (x_{i+1}, u_{i+1}) \ldots , (x_{k}, u_{k}) \} .$$
Sau đó, có một cách trực tiếp để kết luận rằng nếu chúng ta giải "LWE ngược với một bí mật được lặp lại", thì chúng ta có thể giải LWE ngược. Vì LWE ngược là khó nên bài toán của chúng ta cũng khó.
Tuy nhiên, tôi đang gặp khó khăn trong việc xoay quanh sự thật này.
Lưu ý rằng nếu chúng ta không có thuật ngữ lỗi, thì có một cách rất dễ dàng để phân biệt giữa hai trường hợp, ví dụ: $k \geq n+1$. Lưu ý rằng chỉ có thể có $n$ độc lập tuyến tính $x_i$-S. Vì vậy, người phân biệt chỉ tìm kiếm $n$ riêng biệt $x_i$-s trong các mẫu đã cho, lưu ý nơi ma trận $S$ đưa các vectơ này đến và cho $n+1^{\text{th}}$ mẫu riêng biệt, sử dụng tuyến tính để tính toán đầu tiên trong đó $S$ đưa nó đến, và sau đó kiểm tra xem điều đó có phù hợp với những gì được đưa ra hay không.
Tại sao các điều khoản lỗi làm cho bộ phân biệt này không thành công? Ngay cả với lỗi Gaussian, do sự phụ thuộc tuyến tính, không nên $n+1^{\text{th}}$ mẫu riêng biệt có đủ tập trung xung quanh một số giá trị để bộ phân biệt của tôi thành công không?
