Рассмотрим задачу различения полиномиально многих выборок либо
\begin{уравнение}
(x, b, As + e) ~~\text{or}~~\left(x, b, ~Ax + b\cdot(As + e) + e'\right).
\end{уравнение}
Здесь, $А$ является публичной матрицей и $s$ является секретным вектором, выбранным равномерно случайным образом. $е$ и $e'$ являются гауссовыми ошибками. $х$ и $b$ отбираются равномерно случайным образом.
Размеры различных объектов:
\начать{выравнивать}
б &\в \{0, 1\}, \
х &\in \mathbb{Z}_{q}^{n}, \
s &\in \mathbb{Z}_{q}^{n}, \
A &\in \mathbb{Z}_{q}^{m \times n}, \
е, е' &\in \mathbb{Z}_{q}^{m}, \
\end{выравнивание}
$q \geq 2$ является простым целым числом.
Являются ли эти два случая (вычислительно) неразличимыми, когда нам дано полиномиальное количество выборок? Я думаю, что они есть, но я не мог связать их с гипотезой.
Обратите внимание, что LWE,
\begin{уравнение}
(x, b, As + e) ~~\text{and}~~\left(x, b, u\right),
\end{уравнение}
вычислительно неразличимы, и поэтому
\begin{уравнение}
(x, b, ~Ax + b\cdot(As + e) + e') ~~\text{and}~~\left(x, b, ~Ax + b\cdot u + e'\right).
\end{уравнение}
$u$ представляет собой равномерно случайную выборку. Однако я не мог свести свой случай к LWE.
