Điểm:0

Tính không thể phân biệt của hai mẫu loại LWE

lá cờ cn

Xét bài toán phân biệt giữa đa thức nhiều mẫu của một trong hai \begin{phương trình} (x, b, As + e) ​​~~\text{or}~~\left(x, b, ~Ax + b\cdot(As + e) ​​+ e'\right). \end{phương trình}

Đây, $A$ là một ma trận công khai và $s$ là một vectơ bí mật được chọn thống nhất một cách ngẫu nhiên. $e$$e'$ là sai số Gaussian. $x$$b$ được lấy mẫu thống nhất một cách ngẫu nhiên.

Kích thước của các đối tượng khác nhau là:

\begin{align} b &\in \{0, 1\}, \ x &\in \mathbb{Z}_{q}^{n}, \ s &\in \mathbb{Z}_{q}^{n}, \ A &\in \mathbb{Z}_{q}^{m \times n}, \ e, e' &\in \mathbb{Z}_{q}^{m}, \ \end{align}

$q \geq 2$ là một số nguyên tố.


Có phải hai trường hợp này (về mặt tính toán) không thể phân biệt được, khi chúng ta được cung cấp nhiều mẫu đa thức? Tôi nghĩ là có, nhưng tôi không thể liên kết chúng với một phỏng đoán.

Lưu ý rằng bởi LWE,

\begin{phương trình} (x, b, As + e) ​​~~\text{and}~~\left(x, b, u\right), \end{phương trình} không thể phân biệt được về mặt tính toán và cũng vậy \begin{phương trình} (x, b, ~Ax + b\cdot(As + e) ​​+ e') ~~\text{and}~~\left(x, b, ~Ax + b\cdot u + e'\right). \end{phương trình}

$u$ là mẫu ngẫu nhiên đều. Tuy nhiên, tôi không thể giảm trường hợp của mình thành LWE.

Điểm:0
lá cờ ru

Người ta có thể phân biệt tầm thường $(x,0,u)$ từ $(x,0,Ax+eâ)$ bằng cách trừ $Ax$ từ mục thứ ba và xem liệu các mục trông giống nhau hay Gaussian.

phân biệt $(x,1,u)$ từ $(x,1,A(x+s)+(e+eâ))$ là một vấn đề LWE tiêu chuẩn (lưu ý rằng phương sai của $e+eâ$ là tổng các phương sai của $e$$eâ$.

Như vậy mẫu với $b=0$ là tầm thường và mẫu với $b=1$ Có lẽ là không. Lấy đa thức nhiều mẫu hầu như chắc chắn sẽ cho ít nhất một mẫu có $b=0$ và do đó cho phép chúng ta phân biệt một cách tầm thường.

Morbius avatar
lá cờ cn
Chỉ để kiểm tra độ chính xác, nếu có nhiều mẫu đa thức từ một trong hai \begin{equation} (x, b_1, b_2, \ldots, b_k, ~Ax + b_1\cdot(As_1 + e_1) + b_2\cdot(As_2 + e_2) + \cdots + b_k\cdot(As_k + e_k) + e') ~~ \text{or}~~\left(x, b_1, b_2, \ldots, b_k, u \right), \end{equation} cho $b_i \in \{0, 1\}$, cho $k$ lớn đa thức và cho các vectơ bí mật $s_1, \ldots, s_k$, thì chúng sẽ không thể phân biệt được, đúng không?
Morbius avatar
lá cờ cn
Lập luận chỉ là khi mọi $b_i$ là $0$, chúng có thể dễ dàng phân biệt được, nhưng trường hợp như vậy khó xảy ra theo cấp số nhân. Đối với mọi trường hợp khác, với bất kỳ lựa chọn $k$ nào, chúng ta có thể rút gọn nó thành LWE.
Daniel S avatar
lá cờ ru
Không, lập luận là nếu ít nhất $b_i$ bằng 0, tập hợp có thể dễ dàng phân biệt
Morbius avatar
lá cờ cn
Làm thế nào điều đó có thể là sự thật? Giả sử chỉ $b_1 = 0$. Sau đó, về cơ bản, chúng ta đang phân biệt giữa $A(x + s_2 + s_3 + \cdots + s_k) + (e_1 + e_2 + \cdots + e_k) + e'$ và $u$. Đó không phải chỉ là một biến thể của LWE sao? Vì vậy, chúng ta không cần mỗi $b_i$ là $0$ để các mẫu có thể phân biệt được và không chỉ cần ít nhất một $b_i$ là $0$?
Morbius avatar
lá cờ cn
*Chúng tôi đang phân biệt giữa $A(x + s_2 + \cdots + s_k) + (e_2 + \cdots + e_k + e')$ và $u$....
Daniel S avatar
lá cờ ru
Tôi khuyên chúng ta nên chuyển cuộc thảo luận [sang phòng trò chuyện này](https://chat.stackexchange.com/rooms/135597/discussion-on-computational-indistinguiability).

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.