Генерация распределенных случайных чисел

Question

Мне было интересно, есть ли способ для сети из N участников договориться, что число от 1 до M было выбрано случайным образом. (например, на него не влиял ни один из участников) Это было решено для значений n = 2 и m = 2 с помощью протокола подбрасывания монет . Кто-нибудь знает какие-либо решения, которые могут работать для произвольных значений N и M?

Answer 1

Редактировать

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

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

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

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

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

Edit2 - Насколько безопасна вещь хеширования?

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

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

Следовательно, вы должны

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

Answer 2

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

Answer 3

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