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

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

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$ và $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$ và $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.

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.

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.