Современная криптология - Брассар Ж.
Скачать (прямая ссылка):
Любопытной разновидностью подбрасывания жребия являются развлекательные игры, в которых основную роль играет случайность. Особенный интерес представляет покер без карт (mental poker). Каким образом два или более человек могли бы сыграть в покер по телефону, если ни один из них не доверяет другому? Первая схема такой игры (вместе с доказательством ее невозможности при доступе к неограниченным компьютерным ресурсам в случае с двумя игроками) была предложена Эди Шамиром, Рональдом Ривестом и Леонардом Эдлеманом [321], однако Ричард Липтон и Дон Копперсмит продемонстрировали ее ненадежность, поскольку в ней могла произойти утечка частичной информации о картах, которая по предположению всегда должна была оставаться скрытой [251, 121]. Эта специфическая трудность была снята Шафи Гольдвассер и Сильвио Мик-элив [197] применением вероятностного шифрования. Они представили также полное решение задачи, но из него не следовало никакого очевидного способа, как расширить их протокол до протокола для игры с более чем двумя игроками. Безусловно гарантированное решение в том случае, если имеются по крайней мере три игрока и никакие коалиции между ними не допустимы, было предложено Имре Барани и Золтаном Фюреди [14]. Кроме того, для этой задачи различными авторами были даны все более и более тонкие решения [369, 178, 126]. Последнее (теоретическое) решение, в конце концов, было представлено Клодом Крепеу в [127], которое даже позволяет игрокам сохранить суть электронного покера! По поводу обобщений покера на любую игру без карт обращайтесь к работе Одеда Голдрейча, Сильвио Микэли и Эви Вигдерсона [195].
Предположим, что вы являетесь владельцем некоторой ценной секретной информации, такой, например, как разложение
Дополнительные применения 221
на множители вашего главного ключа. Если вы храните его взаперти только в своем офисе, то подвергаетесь риску утратить его при пожаре; если же вы храните несколько копий этого разложения в различных местах, то увеличивается риск того, что одна из них попадет еще в чьи-то руки. (N, к)-пороговая схема позволяет вам распределить вашу тайну по п ее дубликатам таким образом, что для вас будет достаточно иметь доступ к любым к из них, чтобы восстановить весь секрет целиком, тогда как никакие к — 1 из этих п дубликатов не предоставят вам абсолютно никакой информации относительно этого секрета (в смысле теории информации Шеннона). Конструкция этой схемы была разработана независимо Эди Шамиром и Бобом Блэкли [315, 46]. О дальнейших исследованиях на эту тему см. в [243, 22, 92, и т.д.], а также [335].
Пусть Алиса и Боб знают различные секреты, допустим, разложение на множители их соответствующих USA модулей. Предположим также, что они хотят ими обменяться. Как можно осуществить этот обмен секретами так, чтобы ни одна из сторон не подвергалась никакому риску выяснить в конце протокола, что ею только что было получено совсем не то, о чем она договаривалась с другой стороной, в обмен на свой подлинный секрет? Первоначально этот вопрос был изучен Мануэлем Блюмом и Майклом Рабином [50, 299, 52], а затем он привлек внимание многих других исследователей [58, 253, 342, 343, 211]. См. также [366].
Почта с удостоверением (о получении) является усложненной версией цифровой подписи. В этой задаче Алиса хочет послать сообщение Бобу таким способом, чтобы Боб получил это сообщение, если и только если Алисе будет предъявлено подписанное им подтверждение о его получении. Над этой проблемой, поставленной Уитфилдом Диффи, работали Мануэль Блюм и Майкл Рабин [50, 52, 58, 349]. Решающий ее протокол реализует экстремальную (all-or-nothing) удостоверяющую почту — понятие, также введенное Блюмом, которое означает, что получатель не может узнать абсолютно ничего о содержании сообщения до тех пор, пока отправитель не получит подтверждения о его получении, и наоборот [53].
Подписание контрактов еще сложнее (хотя и является достаточно легким для реализации, если использовать в качестве
122 Применения
Глава 6
примитива протокол конкретной почты с удостоверением). Оно позволяет Алисе и Бобу подписывать контракты по компьютерной сети таким образом, что ни один из них не сможет прервать протокол подписывания (за исключением, которое возможно разве что с очень малой вероятностью) и поставить подписи другой стороны под контрактом до тех пор, пока она не будет с ним согласна [52, 300, 58, 168].
Предположим, что вы располагаете некоторым количеством секретов и хотите продать один из них. Раскрывающий протокол позволяет вам сделать это таким способом, что его покупателю будет предоставлена возможность выбора того секрета, который он получит, но не предоставится никакой информации о том, каков именно этот секрет. Такой протокол является экстремальным (all-or-nothing), если у покупателя нет никакой возможности заполучить отдельные биты или целые части нескольких секретов. Эта проблема была сформулирована и решена Жилем Брас-саром, Клодом Крепеу и Жан-Марком Робертом [83, 84], а также, независимо, Дэвидом Чаумом. Ее решение полезно, в частности, при реализации протокола для многостороннего покера без карт, такого как протокол Крепеу [127], и может служить примитивом для более сложных криптографических протоколов. См. также [131].
