Tại sao RLWE khó hoặc thậm chí có giải pháp?

Tôi đã suy nghĩ về lý do tại sao và làm thế nào mà vấn đề RLWE lại khó khăn đến vậy. Tôi biết rằng nó khó vì nó có thể được rút gọn thành bài toán vectơ ngắn nhất, nhưng tôi đang nghĩ làm thế nào để nó có lời giải.

Vấn đề về cơ bản là:

$a_{i}(x)$ là một tập hợp các đa thức ngẫu nhiên nhưng đã biết từ $F_q [ x ] / Φ ( x )$ với các hệ số từ tất cả $F_q$.

$e_i ( x ) $ là một tập hợp các đa thức ngẫu nhiên nhỏ và chưa biết tương đối đến một giới hạn $b$ trong chiếc nhẫn $F_q [ x ] / Φ ( x )$.

$s(x)$ là một đa thức nhỏ chưa biết so với một ràng buộc $b$ bên trong nhẫn $F_q [ x ] / Φ ( x )$.

$b_i ( x ) = ( a_i ( x ) â s ( x ) ) + e_i ( x )$

Bài toán RLWE bao gồm việc tìm đa thức $s$ được cho $b$ và $a$. Nhưng làm thế nào để tôi biết rằng tôi đã tìm thấy nó, nếu lỗi $e$ có thể là bất cứ thứ gì? Ví dụ, tôi có thể chọn một $s$ sao cho kết quả gần với $b$ và phát minh ra bất kỳ $e$ như vậy mà $b = a.s + e$. Từ $e$ là ngẫu nhiên và chưa biết, nó có thể là bất cứ điều gì. Tôi thậm chí không có cách nào để xác minh rằng tôi đã tìm đúng người vì tôi không biết $e$.

Có hai điểm chính mà bạn đang đề cập (một điểm được đề cập bởi Poncho trong các bình luận --- tôi nhắc lại ở đây với mục đích giải thích).

1. Các lỗi RLWE $e_i(x)$ là bé nhỏ, và
2. bí mật $s(x)$ Là nhất quán trên tất cả các mẫu.

Điều này đưa ra một cách khá đơn giản để xác minh rằng bạn đã khôi phục đúng $s(x)$ --- chia đôi bộ mẫu của bạn, phục hồi $s(x)$ từ một nửa số mẫu và xác minh rằng $s(x)$ là như vậy $a(x)s(x)\khoảng b(x)$ (lỗi tối đa "nhỏ") trên nửa mẫu còn lại. Trên tất cả các mẫu, bạn nên xác minh rằng dữ liệu được khôi phục $e(x) = b(x)-a(x)s(x)$ nhỏ. Tôi tin rằng kỹ thuật này được gọi là xác thực chéo trong thống kê, nhưng bất kể nó được gọi là gì thì nó cũng hoạt động tốt ở đây.

Có một điểm khác được đưa ra rằng, tùy thuộc vào các tham số đã chọn, với khả năng cao bạn sẽ có bí mật RLWE là duy nhất (vì vậy bạn có thể chứng minh rằng những lo lắng của mình không thể xảy ra ngay từ đầu, khi tham số hóa thích hợp). Xem ví dụ câu hỏi này để biết chi tiết.