Я новичок в криптографии и пытаюсь формально понять концепции LWE (обучение с ошибками). Я изложу свое понимание определений, которые могут быть неверными.
Определения согласно моему пониманию
Позволять $R$ — конечное унитальное коммутативное кольцо с вероятностью $\му$ (чья $\сигма$-алгебра дискретна). $R$ говорят, чтобы удовлетворить допущение LWE поиска в наихудшем случае если для всех многочленов $n$ и все рандомизированные алгоритмы с полиномиальным временем $S$, карта
\begin{уравнение}
m\mapsto \min_{s\in R^m} p(m,s)\text{,}
\end{уравнение}
куда
\begin{уравнение}
p(m,s) = \Pr\{(A,e)\in R^{m\times n(m)} \times R^{n(m)}: S (-sA+e,A)= с\}\текст{,}
\end{уравнение}
незначительно. В приведенном выше уравнении $А$ выбирается из равномерной вероятности, и $е$ выбирается из вероятности произведения $\му^{п(м)}$.
$R$ говорят, чтобы удовлетворить решение для наихудшего случая, предположение LWE если для всех многочленов $n$ и все рандомизированные алгоритмы с полиномиальным временем $Д$, карта
\begin{уравнение}
m\mapsto \min_{s\in R^m} |p_1(m,s)-p_2(m)|\text{,}
\end{уравнение}
куда
\begin{уравнение}
\начать{разделить}
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\ }\текст{,}
\конец{разделить}
\end{уравнение}
незначительно. В приведенном выше уравнении $А$ и $b$ выбираются из равномерных вероятностей, и $е$ выбирается из вероятности произведения $\му^{п(м)}$.
Вопрос
Я доказал, что если $R$ — конечное поле, снабженное вероятностью $\му$ (чья $\сигма$-алгебра дискретна) и если $R$ удовлетворяет допущению LWE поиска наихудшего случая, тогда $R$ также удовлетворяет допущению LWE о принятии решения для наихудшего случая. Но как доказать обратное? Вся литература, которую я видел до сих пор, просто говорит, что это тривиально, но я не мог этого доказать. Точнее, мне нужно доказательство следующего утверждения:
Если $R$ является конечным унитальным коммутативным кольцом, снабженным вероятностью $\му$ (чья $\сигма$-алгебра дискретна) и если $R$ удовлетворяет наихудшему предположению решения LWE, тогда $R$ также удовлетворяет допущению LWE поиска для наихудшего случая.
Моя попытка
Предположим, что $R$ удовлетворяет допущению LWE для решения наихудшего случая. Позволять $n$ быть многочленом и пусть $S$ быть рандомизированным алгоритмом с полиномиальным временем (входами которого являются элементы $R^{n(m)}\times R^{m\times n(m)}$ и чьи выходы являются элементами в $R^m$). Нам нужно показать, что карта
\begin{уравнение}
m\mapsto \min_{s\in R^m} p(m,s)\text{,}
\end{уравнение}
куда $р(м,с)$ определен выше, пренебрежимо мал. Учитывая ввод $(b,A)\in R^{n(m)}\times R^{m\times n(m)}$ куда $b=-sA+e$, $S$ вернет некоторые предположения $г\в R^m$ который может или не может быть равным $s$. Можно вычислить $b+gA$ и обозначим его через $e'$. Если $г=с$, тогда $е'=е$. Если $g\neq с$, тогда $е'=е$ может держать, а может и не держать.Я не знаю, что теперь делать.
