Phân phối số ngẫu nhiên thế hệ

Question

Tôi đã tự hỏi nếu có một cách để một mạng lưới của N người tham gia đồng ý rằng một số từ 1 đến M được chọn ngẫu nhiên. (ví dụ: không bị ảnh hưởng bởi bất kỳ người tham gia nào) Điều này đã được giải quyết cho các giá trị n = 2 và m = 2 theo số coin tossing protocol. Có ai biết về bất kỳ giải pháp có thể làm việc cho các giá trị tùy ý của N và M?

Answer 1

Sửa

Better thuật toán (nhờ wnoise):

1. Mọi người đều chọn một số bí mật từ 0 đến M-1
2. Mọi người đều gắn thêm một tải của gunk ngẫu nhiên để số lượng và giá trị băm của họ kết quả với một hash an toàn
3. mọi người đều nói với mọi người khác băm này
4. mọi người đều nói với mọi người khác bí mật của họ số, cộng với gunk ngẫu nhiên họ gắn vào nó
5. Mọi người đều xác nhận rằng những con số và băm + trận đấu gunk
6. Thêm tất cả những con số bí mật cùng nhau theo modulo M, sau đó thêm 1 để có được kết quả cuối cùng

Như một người tham gia, tôi nên hài lòng với điều này bởi vì tôi biết rằng tôi đã có ảnh hưởng đầy đủ đến kết quả cuối cùng - con số cuối cùng có thể là bất cứ điều gì cả, tùy thuộc vào sự lựa chọn của tôi về số bí mật. Vì vậy, vì không ai khác có thể dự đoán số của tôi, họ cũng không thể dự đoán được kết quả cuối cùng.

Bất kỳ cách nào để giảm thư từ 3M^2 mà tôi nghi ngờ một cách tiếp cận phát sóng sẽ yêu cầu?

Tôi cho rằng chỉ có ấn phẩm băm là phát sóng, nhưng vẫn là O (M^2). Tôi đoán cách duy nhất xung quanh đó sẽ là trao đổi trước các phím chữ ký số, hoặc để có một trung tâm truyền thông đáng tin cậy.

Chỉnh sửa2 - Làm thế nào an toàn là điều băm?

các cuộc tấn công có thể bao gồm:

1. Nếu tôi có thể tạo ra một vụ va chạm băm sau đó tôi có hai con số bí mật với cùng bảng băm. Vì vậy, một khi tôi biết số bí mật của người khác, tôi có thể chọn số bí mật của mình để tiết lộ, do đó chọn một trong hai kết quả có thể.
2. Nếu tôi tạo số bí mật và thư mục ngẫu nhiên bằng PRNG, thì kẻ tấn công đang cố gắng băm băm của tôi không phải thử mọi số lượng có thể + gunk, chỉ mọi hạt giống có thể cho PRNG.
3. Tôi sử dụng số + gunk mà mọi người tiết lộ để xác định thông tin về PRNG của họ - Tôi có thể cố gắng đoán hoặc brute-buộc các hạt giống, hoặc tính toán trạng thái nội bộ từ đầu ra. Điều này giúp tôi dự đoán những con số nào họ sẽ tạo ra vào lần sau, điều này thu hẹp khoảng trống tìm kiếm cho một cuộc tấn công bạo lực.

Vì vậy, bạn nên

1. Sử dụng một thuật toán băm không gián đoạn đáng tin cậy.
2. Sử dụng trình tạo số ngẫu nhiên an toàn mã hóa có hạt/trạng thái lớn và cố gắng tạo hạt giống từ nguồn entropy tốt.

Answer 2

Đây có lẽ không phải những gì bạn đang tìm kiếm nhưng chỉ để bắt đầu chủ đề này như thế nào về điều này -
Chọn một nhà lãnh đạo, để cho các lãnh đạo chọn số, phân phối số lượng cho mọi người.

Answer 3

Tôi không biết liệu mọi người có thể đồng ý về tính ngẫu nhiên của một số hay không; nó phải nằm trong số liệu thống kê. Nếu số liệu thống kê của nhiều số ngẫu nhiên khớp với số liệu thống kê của các số được lấy từ here thì tôi sẽ xem xét số của bạn ngẫu nhiên, nhưng tôi không biết về người tiếp theo N + 1 trên mạng.