Tôi chưa quen với mật mã và đang cố gắng hiểu các khái niệm về LWE (học có lỗi) một cách chính thức. Tôi sẽ nêu hiểu biết của tôi về các định nghĩa, điều này có thể không chính xác.
Các Định Nghĩa Theo Mình Hiểu
Để cho $R$ là một vành giao hoán đơn vị hữu hạn được trang bị xác suất $\mu$ (của ai $\sigma$-đại số rời rạc). $R$ được cho là thỏa mãn giả định LWE tìm kiếm trong trường hợp xấu nhất nếu với mọi đa thức $n$ và tất cả thuật toán ngẫu nhiên thời gian đa thức $S$, bản đô
\begin{phương trình}
m\mapsto \min_{s\in R^m} p(m,s)\text{,}
\end{phương trình}
ở đâu
\begin{phương trình}
p(m,s) = \Pr\{(A,e)\in R^{m\times n(m)} \times R^{n(m)}: S (-sA+e,A)= s\}\text{,}
\end{phương trình}
không đáng kể. Trong phương trình trên, $A$ được lấy mẫu từ xác suất thống nhất, và $e$ được lấy mẫu từ xác suất sản phẩm $\mu^{n(m)}$.
$R$ được cho là thỏa mãn quyết định trường hợp xấu nhất LWE giả định nếu với mọi đa thức $n$ và tất cả thuật toán ngẫu nhiên thời gian đa thức $D$, bản đô
\begin{phương trình}
m\mapsto \min_{s\in R^m} |p_1(m,s)-p_2(m)|\text{,}
\end{phương trình}
ở đâu
\begin{phương trình}
\start{split}
p_1(m,s) &= \Pr\{(A,e)\in R^{m\times n(m)}\times R^{n(m)}: D (-sA+e,A) =1\},\
p_2(m) &= \Pr\{(b,A)\in R^{n(m)}\times R^{m\times n(m)}\times: D (b,A)=1\ }\chữ{,}
\end{tách}
\end{phương trình}
không đáng kể. Trong phương trình trên, $A$ và $b$ được lấy mẫu từ các xác suất thống nhất, và $e$ được lấy mẫu từ xác suất sản phẩm $\mu^{n(m)}$.
Câu hỏi
Tôi đã chứng minh rằng nếu $R$ là một trường hữu hạn được trang bị xác suất $\mu$ (của ai $\sigma$-đại số rời rạc) và nếu $R$ thỏa mãn giả định LWE tìm kiếm trong trường hợp xấu nhất, sau đó $R$ cũng thỏa mãn giả định LWE quyết định trong trường hợp xấu nhất. Nhưng làm thế nào để chứng minh điều ngược lại? Tất cả các tài liệu tôi đã xem cho đến nay chỉ nói rằng nó tầm thường, nhưng tôi không thể chứng minh điều đó. Rõ ràng hơn, tôi cần một bằng chứng về tuyên bố sau:
Nếu $R$ là một vành giao hoán đơn vị hữu hạn được trang bị xác suất $\mu$ (của ai $\sigma$-đại số rời rạc) và nếu $R$ thỏa mãn giả định LWE quyết định trường hợp xấu nhất, sau đó $R$ cũng thỏa mãn giả định LWE tìm kiếm trong trường hợp xấu nhất.
Nỗ lực của tôi
Giả sử $R$ thỏa mãn giả định LWE quyết định trong trường hợp xấu nhất. Để cho $n$ là một đa thức và để cho $S$ là một thuật toán ngẫu nhiên thời gian đa thức (có đầu vào là các phần tử trong $R^{n(m)}\times R^{m\times n(m)}$ và có đầu ra là các phần tử trong $R^m$). Chúng ta cần chỉ ra rằng bản đồ
\begin{phương trình}
m\mapsto \min_{s\in R^m} p(m,s)\text{,}
\end{phương trình}
ở đâu $p(m,s)$ được xác định ở trên, là không đáng kể. Đưa ra một đầu vào $(b,A)\in R^{n(m)}\times R^{m\times n(m)}$ ở đâu $b=-sA+e$, $S$ sẽ trả lại một số dự đoán $g\trong R^m$ điều đó có thể hoặc có thể không bằng $s$. Người ta có thể tính toán $b+gA$ và biểu thị nó bằng $e'$. Nếu $g=s$, sau đó $e'=e$. Nếu $g\neq s$, sau đó $e'=e$ có thể hoặc không thể giữ.Tôi không biết phải làm gì bây giờ.
