Tham gia Đăng nhập
Điểm:0
Sean avatar Crypto

tính toán không thể phân biệt

lá cờ yt
Sean

Cho một nhóm cấp số nhân $q$ và mô đun $p$. Cho hai hằng số $a$ và $b$ lấy mẫu ngẫu nhiên từ $Z_q$. Để biến ngẫu nhiên $x_a$ là một cặp $(x, x^a \mod p)$ và biến ngẫu nhiên $x_b$ là một cặp $(x, x^b \mod p)$. Liệu sự phân phối của $x_a$ và $x_b$ có thể phân biệt được về mặt tính toán?

67
1 + 2
Sean avatar
lá cờ yt
Sean
Ở đây $a$ và $b$ đã biết, nếu không, quyết định rất đơn giản: vì a đã biết, chỉ cần lấy $a^{-1}$ và cặp đã cho $(x, x^a)$ áp dụng $(x^ a)^{1/a}$ và kiểm tra xem nó có bằng $x$ hay không.
0
Hồi đáp
Mark avatar
lá cờ ng
Mark
Ý bạn là $a$ và $b$ là *unknown*?
0
Hồi đáp
Điểm:1
Yehuda Lindell avatar Crypto
lá cờ us
Yehuda Lindell

Câu hỏi gây nhầm lẫn trong việc sử dụng thuật ngữ "hằng số". Tuy nhiên, nó nói lấy mẫu ngẫu nhiên. Vậy biến ngẫu nhiên là $(x,x^a \bmod p)$ ở đâu $a$ là ngẫu nhiên trong $\mathbb{Z}_q$. Nếu đây là trường hợp, thì hai bản phân phối giống hệt nhau. Chúng chỉ là cùng một phân phối với các ký hiệu khác nhau cho giá trị được lấy mẫu ngẫu nhiên.

0 + 8
Sean avatar
lá cờ yt
Sean
Cảm ơn vì bạn đã phản hồi. Tôi vẫn còn bối rối một chút. Với một cặp $(x, x^a)$, tôi có cho rằng xác suất xuất hiện của nó trong lần phân phối thứ 2 sẽ là 0 không? Nói cách khác, $a$ và $b$ được cố định cho lần phân phối thứ nhất và thứ hai. $x$ được lấy mẫu ngẫu nhiên và sau đó nó dẫn đến bộ $(x,x^a)$ và $(x, x^b)$.
0
Hồi đáp
Yehuda Lindell avatar
lá cờ us
Yehuda Lindell
Tôi nghĩ rằng tôi đã hiểu sai câu hỏi. Có phải không gian xác suất chỉ dành cho lựa chọn $x$, chứ không phải $a$ hoặc $b$? Trong trường hợp đó, các bản phân phối được phân biệt tầm thường.
0
Hồi đáp
Sean avatar
lá cờ yt
Sean
Cảm ơn các đầu vào! Tôi đang tự hỏi ý tưởng để phân biệt hai ý tưởng này bằng một chương trình hiệu quả là gì? Với $x$, làm thế nào để máy xác suất cho biết sự khác biệt giữa $x^a$ và $x^b$ nếu $a$ và $b$ không xác định? Có vẻ như cần rất nhiều mẫu (của 2 phân phối) để tìm ra một cặp xung đột?
0
Hồi đáp
Yehuda Lindell avatar
lá cờ us
Yehuda Lindell
Có sự nhầm lẫn ở đây. Không có cái đã biết và cái chưa biết. Nếu chúng là cố định thì chúng được coi là đã biết. Nếu chúng không xác định, thì điều đó có nghĩa là chúng được chọn ngẫu nhiên và đó là cùng một biến ngẫu nhiên. Tất nhiên, có thể có trường hợp một $a$ duy nhất được chọn và sau đó nhiều cặp với các $x$ ngẫu nhiên khác nhau được đưa ra tương ứng với cùng một $a$. Điểm mấu chốt, điều này không được xác định rõ.
0
Hồi đáp
Sean avatar
lá cờ yt
Sean
Tôi đoán tôi sẽ phải viết lại câu hỏi của mình:
0
Hồi đáp
Sean avatar
lá cờ yt
Sean
Để tôi viết lại câu hỏi: giả sử $P_a$ là một cỗ máy xác suất biết bí mật $a$ và tạo ra một chuỗi các bộ giá trị $n$: $(x_1, {x_1}^{a}), ..., (x_n , {x_n}^a)$ trong đó $x_i$ cho mỗi bộ được lấy mẫu ngẫu nhiên. Tương tự, hãy xác định một PPT $P_b$. Bây giờ, hãy để một người thách đấu chọn ngẫu nhiên hai chuỗi được tạo bởi $P_a$ và $P_b$ (chúng có thể là cả hai từ $P_a$ hoặc một từ $P_a$ và một từ $P_b$). Người ta có thể biết liệu hai chuỗi có được tạo bởi hai PPT khác nhau không?
0
Hồi đáp
Yehuda Lindell avatar
lá cờ us
Yehuda Lindell
Chỉ $P_a$ biết $a$, hay bộ phân biệt cũng biết $a$? Nếu trước đây, thì các bản phân phối giống hệt nhau về mặt thống kê; nếu cái sau, thì các bản phân phối được phân biệt một cách tầm thường.
0
Hồi đáp
Sean avatar
lá cờ yt
Sean
Cảm ơn vì sự trả lời! Máy phân biệt không biết $a$, $b$. Vì vậy, điều đó giải quyết vấn đề của tôi sau đó. Cảm ơn một lần nữa!
0
Hồi đáp
lá cờ VietNam
Phan Văn Trường
Câu hỏi này là trong các ngôn ngữ khác:

Đă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.