Генерация распределенного случайного числа

Ответ 1

Edit

Лучший алгоритм (спасибо wnoise):

• Каждый выбирает секретный номер от 0 до M-1
• Каждый добавляет нагрузку случайного gunk к своему числу и хеширует результат с помощью безопасного хэша
• Все говорят всем, что этот хэш
• Все говорят каждому другому свой секретный номер, плюс случайный мусор, к которому они присоединяются.
• Каждый проверяет соответствие чисел и хэшей + gunk
• Добавьте все секретные числа вместе по модулю M, затем добавьте 1, чтобы получить окончательный результат

Как участник, я должен быть доволен этим, потому что я знаю, что я имел полное влияние на конечный результат - окончательное число могло быть вообще чем угодно, в зависимости от моего выбора секретного номера. Поэтому, поскольку никто другой не мог предсказать мой номер, они также не могли предсказать конечный результат.

Любой способ уменьшить сообщения от 3M ^ 2, которые, как я подозреваю, потребует широковещательный подход?

Я считаю, что только хеш-публикация должна быть широковещательной, но она все еще O (M ^ 2). Я предполагаю, что единственный способ - это обмен ключами цифровой подписи или наличие надежного узла связи.

Edit2. Насколько безопасно это хеширование?

Возможные атаки включают:

• Если я могу создать хэш-столкновение, тогда у меня есть два секретных номера с одинаковым хэшем. Поэтому, когда я знаю все остальные секретные номера, я могу выбрать, какие из моих секретных номеров вывести, выбрав один из двух возможных результатов.
• Если я создаю свой секретный номер и случайный мусор с помощью PRNG, тогда злоумышленник, пытающийся переборщить мой хэш, не должен пытаться использовать все возможные числа + gunk, только все возможные семена для PRNG.
• Я использую число + gunk, которое каждый обнаруживает, чтобы определить информацию об их PRNG - я мог бы попытаться угадать или переборщить семена или вычислить внутреннее состояние с выхода. Это помогает мне предсказать, какие числа они будут генерировать в следующий раз, что сужает пространство поиска для атаки грубой силы.

Поэтому вы должны

• Использовать надежный, непрерывный алгоритм хэширования.
• Используйте криптографически безопасный генератор случайных чисел, который имеет большое семя/состояние, и попытайтесь высеять его из хорошего источника энтропии.

Ответ 2

Я не знаю, можно ли людям договориться о случайности одного числа; это должно быть в статистике. Если статистика многих случайных чисел соответствовала статистике чисел, взятых из здесь, я бы рассмотрел ваш номер случайным образом, но я не знаю о следующего парня N + 1 в сети.

Ответ 3

Это, вероятно, не то, что вы ищете, а просто начать эту тему, как об этом -
Выберите лидера, пусть лидер выбирает номер, распределяет его всем.