Vâng, vì lý do chung.
cụ thể là, $a$ khả nghịch là:
- Có thể kiểm chứng công khai, và
- xảy ra với xác suất không đáng kể $p$ (về sự lựa chọn thống nhất của $a$), xem cái này để biết chi tiết.
Bất cứ khi nào bạn gặp một tình huống như thế này, trước tiên bạn có thể yêu cầu bất kỳ đối thủ giả định nào kiểm tra xem điều kiện có đúng không và nếu không thì hãy "đoán" câu trả lời một cách ngẫu nhiên.
Điều này làm giảm lợi thế theo hệ số nhân $p$, nhưng vì điều này không đáng kể nên nó không thành vấn đề (ít nhất là đối với các khái niệm tiệm cận về bảo mật).
Đây chính xác là lời giải thích được đưa ra trong bài báo Steinfield và Stehle mà bạn đã liên kết, nhưng nó không liên quan gì đến "vấn đề cơ bản" mà họ đang giải quyết là RLWE với các bí mật thống nhất và tuân theo tính tổng quát mà tôi đã đề cập ở trên.
Độc lập với những điều trên, đây là Mà còn một động lực để giảm trường hợp xấu nhất đến trường hợp trung bình trong mật mã mạng.
Thông thường, có một số ứng cử viên "hiển nhiên" cho một vấn đề khó khăn (ví dụ như bao thanh toán hoặc BDD/CVP cho mạng), nhưng việc xác định phân phối trường hợp trung bình chính xác để sử dụng có thể không rõ ràng.
Việc giảm trường hợp xấu nhất đến trường hợp trung bình cho thấy rằng một số phân phối trường hợp trung bình cho các vấn đề LWE không phải là "xấu về mặt cấu trúc", ví dụ:
- đồng phục $a$, đồng phục $s$, gaussian $e$ (độ lệch chuẩn $\geq \Omega(\sqrt{n})$, lớn hơn hầu hết mọi người sử dụng trong thực tế)
- đồng phục $a$, $s$ tuân theo sự phân bố của $e$
Một khi chúng ta biết rằng đồng phục $a$ là phân phối "đúng" để làm việc, chúng ta có thể tự do áp đặt bất kỳ điều kiện "lớn" nào (có nghĩa là xảy ra với xác suất không đáng kể) mà chúng ta muốn $a$, bao gồm cả việc nó không thể đảo ngược (hoặc có tọa độ đầu tiên $1$, hoặc có $\sum_i a_i \equiv 0 \bmod q$ cho đa thức lớn $q$, hoặc về cơ bản bất cứ điều gì). Lưu ý rằng điều này chỉ đúng tiệm cận mặc dù --- việc giảm trường hợp xấu nhất đến trường hợp trung bình không đặc biệt hữu ích trong việc tham số hóa LWE một cách cụ thể, vì người ta có thể biện minh cho các tham số nhỏ hơn bằng cách trực tiếp phân tích mã hóa LWE.
