Позволять $q \geq 2$ быть простым целым числом. Рассмотрим две функции, заданные формулой:
$$f(b, x) = Ax + b \cdot u + e~~~(\text{mod}~q),$$
$$g(b, x) = Ax + b \cdot (As + e') + e~~~(\text{mod}~q),$$
где у нас есть:
\начать{выравнивать}
б &\в \{0, 1\}, \
х &\in \mathbb{Z}_{q}^{n}, \
s &\in \mathbb{Z}_{q}^{m}, \
A &\in \mathbb{Z}_{q}^{n \times m}, \
е' &\in \mathbb{Z}_{q}^{m}, \
u &\in \mathbb{Z}_{q}^{m},
\end{выравнивание}
$е$ выбирается из дистрибутива:
\begin{уравнение}
D _ {\ mathbb {Z} _q, B ^ {'}} (x) = \ frac {e ^ {\ frac {- \ pi || x || ^ {2}} {B ^ {'2}}} }{\sum_{x \in \mathbb{Z}_q^{n}, ||x|| \leq B'} e^{\frac{- \pi ||x||^{2}}{B^{'2}}}},
\end{уравнение}
куда
$$B' = \frac{q}{C_{T} \sqrt{mn \log q}},$$
$C_{T}$ является фиксированной константой.
В это бумаги, функции определены в уравнении 29, и упоминается, что в худшем случае более $А$, $u$ и $e'$, предполагая, что LWE сложна для классических алгоритмов с полиномиальным временем, различая $f$ и $г$ также трудно, учитывая $А$ и даны (полиномиально много) «выборки» (поскольку $е$ представляет собой распределение вероятностей, выходы $f$ или же $г$ являются образцами) из любого $f$ или же $г$.
Сокращение LWE также справедливо для среднего случая.
В документе также упоминается, что эти две функции представляют собой семейство «расширенных функций без когтей-ловушек (определение 5, 6, 7)».
В качестве ссылки на доказательство этих вышеприведенных фактов в статье упоминается это бумага (лемма 9.3). Однако при доказательстве леммы 9.3 вторая статья также ссылается на некоторые другие работы, например это один. Доказательство не было ясно мне ни в одной из статей.
Я хотел спросить, как уменьшить задачу различения между $f$ и $г$ к ЛВЕ. Я также хотел спросить о важности функции «расширенная лазейка без когтей» в этом сокращении.
Насколько я понимаю, жесткость LWE говорит о том, что если нам дано $А$, различая равномерно случайные выборки и выборки из $As + e'$ это трудно. я не знаю как $b$ и $х$ или другие параметры влияют на этот факт. Это то, где нам нужно доказательство отсутствия клешней с расширенной дверью-ловушкой?
