Лотерея, в которой можно убедиться, что это честно

27

(Извините, если это хорошо известно.) Я хотел бы передать какой-то предмет одному из агентов, чтобы агент получил предмет с вероятностью . Существует ли криптографический (или другой) инструмент, позволяющий каждому агенту (и даже каждому наблюдателю) быть уверенным в том, что случайное рисование действительно справедливо? $k$ $j$ $p_i$

cr.crypto-security Гил Калай
источник

1

Разрешено ли агентам знать .. ?

p_{0}

$p_0$

p_{k}

$p_k$

Майк Сэмюэль

Вы видели это? ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4232861

dspyz

19

Если я понять проблему правильно, по- видимому, количество общественных листать односторонний монету. Кажется, есть много способов сделать это, если вы берете на себя обязательства. Одним из примеров было бы то, чтобы каждая сторона генерировала случайное целое число от 0 до , используя обязательство по битам для публичной фиксации этой строки битов. Затем, как только каждый агент совершил, они все публично раскрывают свое секретное целое число. Тогда выигрышным агентом будет индексированный по сумме целых чисел по модулю . Если хотя бы один агент честен, то переворот должен быть случайным. $k$ $k-1$ $k$

Конечно, одна из проблем заключается в том, что это требует определенных усилий. Информационно-теоретические схемы для битовой привязки невозможны как для классических, так и для квантовых вычислений (хотя Адриан Кент недавно предложил схему, использующую относительность). Тем не менее, безопасное выделение битов может быть достигнуто с вычислительными допущениями.

Джо Фитцсимонс
источник

2

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

Zsbán Ambrus

1

@ user8067: Я не верю, что это возможно без взаимодействия или доверия, что хотя бы одна сторона честна. Причина, по которой я это говорю, заключается в том, что если первоначальная случайность на самом деле предопределена заговором всех, кто участвует в этой точке, тогда весь процесс является детерминированным, а не случайным. Однако проблема требует, чтобы процесс был случайным, так что это лучшее, что вы можете сделать.

Джо Фицсимонс

2

Я не уверен, что это возможно.

Джо Фицсимонс

2

@RickyDemer: В вопросе недостаточно информации, чтобы сказать, какая модель противника здесь применима. Если бы Гил сказал нам точно, для чего он нужен, то было бы легче доказать, соответствует ли конкретная схема его требованиям. Тем не менее, я не сомневаюсь, что Гил более чем способен проверить, отвечают ли наши ответы его потребностям.

Джо Фицсимонс

2

@RickyDemer: Мне не совсем понятно, какова очевидная модель для этого случая. Это сильно зависит от настройки, и не очевидно, какими должны быть предположения по умолчанию. Немного понизить голос и начать вести себя так, будто мой ответ и Лев неправильны. Они явно не включают оговорку, указанную в ответе Адама. Обратите внимание, что я не редактирую свой ответ, потому что без дополнительной информации от Джила я не вижу смысла гадать о модели противника, и поэтому я оставляю ее как можно более общей (не уточняя, немного обязательство должно быть не изменчивым).

Джо Фицсимонс

15

Как намекают другие пользователи, это хорошо изученная проблема в криптографии. Это называется «подбрасывание монет» и является частным случаем многопартийных вычислений.

Какой протокол выполняет работу, зависит от контекста.

В «автономном» режиме протокол будет работать изолированно, без одновременного участия игроков в других протоколах (или даже в любом взаимодействии с внешним миром). Это прекрасно описано в учебнике Одеда Голдрайха «Основы криптографии» (я думаю, том 2).

Просто чтобы дать представление о том, насколько тонким он является, протокол «каждый принимает на себя случайные значения», предложенный другим респондентом, небезопасен, если используемая вами схема фиксации является гибкой. Схемы невыполнимых обязательств дают вам безопасный протокол, но их немного сложно спроектировать.

В настройках, где участники участвуют в других одновременных протоколах, вы хотите протокол, который является составным . Существуют различные понятия о возможности компоновки, но наиболее сильное понятие , называемое универсальной компоновкой , требует некоторых дополнительных допущений при настройке (например, PKI или общая случайная строка, видимая всем сторонам, но не контролируемая ни одной из них). Я не знаю доступного лечения этой темы, к сожалению. Но было бы неплохо начать с недавнего исследования, посвященного универсальной компостируемости или непоколебимой приверженности.

Адам Смит
источник

1

«Общая случайная строка, видимая всем сторонам, но не контролируемая ни одной из них» - это именно то, что мы хотим сгенерировать.

Zsbán Ambrus

1

и однажды решив эту проблему, можно универсально

$\hspace{1 in}$ решить это снова (произвольно много раз).

$\:$

Я думаю, что обязательство UC известно настройкой Registered Public Key (что является более сильным предположением, чем PKI) и установкой с несколькими строками (которая является более слабым предположением, чем обычная случайная строка).

2

Добро пожаловать на сайт, Адам!

Гил Калай

11

Примечание: пожалуйста, прочитайте комментарии ниже. Этот протокол, похоже, имеет проблемы.

$p_j$

$\{0,1\}^b$ $b$

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

Лев Рейзин
источник

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

Джо Фитцсимонс

Не стоит беспокоиться! Кажется, мы на правильном пути.

Лев Рейзин

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

Джо Фицсимонс

7

Самое раннее упоминание, которое я знаю, это: М. Блум. Монета листает по телефону. КРИПТО 1981: 11-15. Можно загрузить по адресу dm.ing.unibs.it/giuzzi/corsi/Support/papers-cryptography/…

Райан Уильямс,

4

Существует стандартная атака, если вы используете стандартные схемы фиксации битов (например, хеширование). Давайте рассмотрим случай с двумя сторонами, Алисой и Бобом, куда Алиса идет первой. После того, как Алиса передает свое обязательство, Боб может скопировать его. После того, как Алиса открывает свое обязательство, Боб может открыть его сейчас же. Теперь их случайные векторы равны, поэтому они обращаются к нулю - Бобу удалось довести конечное значение до нуля, что противоречит требованию справедливости.

DW

-3

Пассивные наблюдатели не могут проверить, что чертеж не был поставлен. Входы в псевдослучайный процесс могут быть выбраны, чтобы дать желаемый результат.

Однако, если наблюдатель может предоставить случайное число, которое, как он знает, является случайным, и убедиться, что другие агенты не изменят свои входные данные впоследствии (потому что они могут компенсировать его эффект своими входными данными), то он может быть уверен, что результат действительно был случайным ,

Это требует схемы обязательств, которую мы не знаем, которая математически доказана как безопасная, но на практике может быть реализована с использованием безопасного хэша (такого как SHA3).

Рассмотрим этот пример:

введите описание изображения здесь

Я сделал пример реализации. Вы можете увидеть его в прямом эфире здесь: https://mrogalski.eu/cl/ или проверить источники на GitHub .

Марек Рогальский
источник

1

Это уже отмечено в ответе Джо.

Каве

1

Графическая иллюстрация очень хорошая!

Гил Калай

3

Графика очень красивая, но ваш ответ не содержит ничего, чего нет в существующих ответах.

Дэвид Ричерби

Лотерея, в которой можно убедиться, что это честно

Ответы: