Bằng chứng rằng bí mật (ring-)LWE là duy nhất

của Regev Khảo sát LWE chứa một bản phác thảo của bằng chứng.

thuật toán. Một cách đơn giản để giải quyết LWE là thông qua thuật toán khả năng tối đa. Giả sử cho đơn giản rằng $q$ là đa thức và phân phối lỗi là bình thường, như trên. Khi đó, không khó để chứng minh rằng sau khoảng $O(n)$ phương trình, nhiệm vụ duy nhất để $s$ rằng "thỏa mãn gần đúng" các phương trình là phương trình đúng. Điều này có thể được chứng minh bằng một đối số chuẩn dựa trên giới hạn Chernoffâ và liên kết giới hạn trên tất cả $s\in\mathbb{Z}_q^n$. Điều này dẫn đến một thuật toán chỉ sử dụng $O(n)$ mẫu, và chạy trong thời gian $2^{O(n \log n)}$. Như một hệ quả tất yếu, chúng tôi nhận được rằng LWE được "xác định rõ" theo nghĩa là với xác suất cao giải pháp $s$ là duy nhất, giả sử số phương trình là $\Omega(n)$.

Cũng có thể hữu ích khi xem LWE từ một góc nhìn khác --- cụ thể là phạm vi tham số cho SIS ở vị trí của nó tiên nghiệm không rõ liệu một giải pháp có nên tồn tại hay không, vì vậy người ta "trồng" một giải pháp. Nhìn thấy những ghi chú này cho một số quan điểm dọc theo những dòng này. Lưu ý rằng đối với SIS tiêu chuẩn, nhiều giải pháp tồn tại với xác suất cao, vì vậy "LWE = SIS quyết định (trong một số phạm vi tham số)" rất dễ bị nhầm lẫn nếu không cẩn thận, xem ví dụ câu hỏi này.