Để cho $q \geq 2$ là một số nguyên tố. Hãy xem xét hai chức năng, được đưa ra bởi:
$$f(b, x) = Ax + b \cdot u + e~~~(\text{mod}~q),$$
$$g(b, x) = Ax + b \cdot (As + e') + e~~~(\text{mod}~q),$$
nơi chúng tôi có:
\begin{align}
b &\in \{0, 1\}, \
x &\in \mathbb{Z}_{q}^{n}, \
s &\in \mathbb{Z}_{q}^{m}, \
A &\in \mathbb{Z}_{q}^{n \times m}, \
e' &\in \mathbb{Z}_{q}^{m}, \
u &\in \mathbb{Z}_{q}^{m},
\end{align}
$e$ được lấy mẫu từ phân phối:
\begin{phương trình}
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{phương trình}
ở đâu
$$B' = \frac{q}{C_{T} \sqrt{mn \log q}},$$
$C_{T}$ là một hằng số cố định.
Trong cái này giấy, các chức năng được xác định trong phương trình 29 và nó được đề cập rằng trong trường hợp xấu nhất trên $A$, $u$ và $e'$, giả sử LWE khó đối với các thuật toán cổ điển thời gian đa thức, phân biệt giữa $f$ và $g$ cũng khó, đưa ra $A$ và đưa ra (đa thức nhiều) "mẫu" (vì $e$ là một phân phối xác suất, đầu ra của $f$ hoặc $g$ là các mẫu) từ một trong hai $f$ hoặc $g$.
Việc giảm LWE cũng giữ cho trường hợp trung bình.
Bài báo cũng đề cập rằng hai chức năng này là một họ "các chức năng không có cửa bẫy mở rộng (Định nghĩa 5, 6, 7.)"
Như một tài liệu tham khảo để chứng minh các sự kiện trên, tài liệu tham khảo bài viết cái này giấy (Bổ đề 9.3). Tuy nhiên, trong khi chứng minh Bổ đề 9.3, bài báo thứ hai cũng tham khảo một số bài báo khác, như cái này một. Bằng chứng không rõ ràng đối với tôi trong bất kỳ bài báo nào.
Tôi muốn hỏi làm thế nào để giảm bớt nhiệm vụ phân biệt giữa $f$ và $g$ đến LWE. Tôi cũng muốn hỏi về tầm quan trọng của chức năng "không có cửa bẫy mở rộng" trong việc giảm thiểu đó.
Theo hiểu biết của tôi, độ cứng của LWE nói rằng nếu chúng ta được cho $A$, phân biệt giữa các mẫu ngẫu nhiên thống nhất và các mẫu từ $As + e'$ khó. tôi không chắc làm thế nào $b$ và $x$ hoặc các tham số khác ảnh hưởng đến thực tế đó. Đó có phải là nơi chúng ta cần bằng chứng mở rộng cửa bẫy không?
