Điểm:2

Hai người không tin tưởng muốn đưa ra một con số ngẫu nhiên

lá cờ cn

Hai người muốn đưa ra một con số ngẫu nhiên. Họ không tin tưởng lẫn nhau cũng như bất kỳ bên thứ ba nào. Các giải pháp đã biết cho vấn đề này là gì?

Tôi là một sinh viên mật mã lượng tử và hiện đang làm công việc tạo số ngẫu nhiên lượng tử.Bất kỳ giải pháp nào, cổ điển hoặc lượng tử đều được hoan nghênh.

CHỈNH SỬA

Ok, đây là những gì tôi hiểu bằng cách đọc qua một số bài báo. Giả sử hai bên không tin tưởng muốn đưa ra một chút ngẫu nhiên. Trong kịch bản cổ điển (không giả định độ cứng tính toán), nhiệm vụ là không thể. Trong kịch bản lượng tử, có hai biến thể; phiên bản mạnh và yếu. Nếu kết quả mong muốn của mỗi bên là không phải biết nó được gọi là phiên bản mạnh và ngược lại. Phiên bản mạnh có giới hạn khác không đối với độ lệch của nó trong khi phiên bản yếu có thể có độ lệch nhỏ tùy ý.

https://arxiv.org/pdf/1911.13283.pdf

Frédéric Grosshans avatar
lá cờ co
Không phải là một câu trả lời, nhưng chỉ để giúp tìm kiếm của bạn: vấn đề này được gọi là tung đồng xu
Dotman avatar
lá cờ cn
Cảm ơn vì điều đó. Điều đó thực sự có ích!
Điểm:5
lá cờ es

Số ngẫu nhiên được yêu cầu là một số nguyên trong khoảng từ 0 đến $\ell$. Mỗi người chọn một số ngẫu nhiên $x_i$ giữa 0 và $\ell$, mỗi người chọn một $n$-bit yếu tố mù ngẫu nhiên $b_i$ ở đâu $n\geq 128$$n$ phải được thỏa thuận trước. Mỗi sau đó thông báo một cam kết băm được tính như $H(b \mathbin\|x)$. Sau đó, mỗi người mở các cam kết của mình bằng cách thông báo các giá trị của họ về $b$$x$, và tính toán số ngẫu nhiên của họ là $$x_1 + x_2\ \pmod \ell.$$ Điều này là an toàn lượng tử nếu hàm băm và lựa chọn của $n$ cùng an toàn lượng tử.

Như @poncho đã chỉ ra, người mở cam kết cuối cùng của họ có thể mô phỏng lỗi không hoàn thành giao thức nếu họ không hài lòng với giá trị ngẫu nhiên được chia sẻ cụ thể sẽ được tạo trong quá trình gọi giao thức đó.Đây có thể là một vấn đề đặc biệt nếu $\ell$ nhỏ.

Một cách để tránh vấn đề này là đảm bảo rằng sẽ bị mất quyền nếu không hoàn thành giao thức. Ví dụ: mỗi người có thể gửi tiền với một trọng tài viên đáng tin cậy, người sẽ tịch thu những khoản tiền đó từ người không hoàn thành giao thức. Số tiền bị mất phải bằng hoặc vượt quá mức thu được tối đa có thể từ việc mô phỏng lỗi.

poncho avatar
lá cờ my
Một cuộc tấn công chống lại giao thức này là một cuộc tấn công 'lỗi mô phỏng'; giả sử Alice chọn $x_1$ và Bob chọn $x_2$; họ thực hiện giao thức và Alice mở cam kết của mình với $x_1$. Bây giờ, Bob thấy rằng anh ấy không thích kết quả $x_1 + x_2 \bmod \ell$, và vì vậy anh ấy mô phỏng một lỗi (lỗi mạng, khởi động lại máy tính, bất cứ điều gì). Điều này có thể được giải quyết bằng một siêu giao thức; điều quan trọng là bạn phải làm như vậy
knaccc avatar
lá cờ es
@poncho cảm ơn, điểm tuyệt vời
kelalaka avatar
lá cờ in
Nếu có một lỗi thực sự thì sao? Tại sao một người trung thực nên mất tiền trong trường hợp này?
knaccc avatar
lá cờ es
@kelalaka Một người trung thực nên tiếp tục (thay vì khởi động lại hoặc từ bỏ) giao thức ngay khi các khó khăn kỹ thuật được giải quyết và sẽ không bị mất. Một người không trung thực sẽ muốn từ bỏ giao thức và không bao giờ tiếp tục nó.
Điểm:1
lá cờ in

Manuel Blaum đã xem xét vấn đề này vào năm 1981 trong Lật đồng xu qua điện thoại Một giao thức để giải quyết các vấn đề bất khả thi

Các chi tiết kỹ thuật là trên giấy. Giao thức này đảm bảo những điều đó (từ bài báo, in đậm là ý);

  1. Nếu một trong hai người tham gia tuân theo giao thức không bắt được người kia gian lận, người đó có thể chắc chắn rằng mỗi đồng xu có xác suất độc lập chính xác là 50-50 để đi lên (có thể chứng minh được với giả định hợp lý rằng bao thanh toán là khó.
  2. Nếu một trong hai người tham gia bắt được người kia gian lận, người đó có thể chứng minh điều đó với thẩm phán (điều này giả định rằng tất cả các tin nhắn được gửi đã được ký).
  3. Sau khi Bob tung đồng xu cho Alice, cô ấy biết đồng xu nào ngửa, đồng nào ngửa. Anh ta hoàn toàn KHÔNG biết làm thế nào họ nghĩ ra (thậm chí không phải là một dự đoán tốt).
  4. Sau chuỗi tung đồng xu, Alice sẽ có thể chứng minh cho Bob thấy đồng xu nào ngửa, đồng nào ngửa.
Điểm:1
lá cờ cn

tôi nghĩ tờ giấy này giải quyết ít nhất một phần vấn đề của bạn.

kelalaka avatar
lá cờ in
Chúng tôi gọi đây là câu trả lời chỉ liên kết và coi đó là một nhận xét. Bạn có thể giải thích một chút những gì giấy này?
Dotman avatar
lá cờ cn
Điều này thực sự hữu ích... @kelalaka Tôi sẽ cố gắng thêm nhận xét khi tôi hiểu nó
Dotman avatar
lá cờ cn
Ok, đây là những gì tôi hiểu bằng cách đọc qua một số bài báo. Giả sử hai bên không tin tưởng muốn đưa ra một chút ngẫu nhiên. Trong kịch bản cổ điển (không giả định độ cứng tính toán), nhiệm vụ là không thể. Trong kịch bản lượng tử, có hai biến thể; phiên bản mạnh và yếu. Nếu kết quả mong muốn của mỗi bên là **không** được biết thì đó được gọi là phiên bản mạnh mẽ và ngược lại. Phiên bản mạnh có giới hạn khác không đối với độ lệch của nó trong khi phiên bản yếu có thể có độ lệch nhỏ tùy ý.

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