![]() |
Геовикипедия wiki.web.ru | |
|
|
|
Н. В. Гоголь. ``Мертвые души'', глава 5. В данном разделе мы кратко обсудим те типы криптографических протоколов, в которых два участника должны обменяться некоторой информацией. Но участники не доверяют друг другу и каждый из них может оказаться обманщиком. Поэтому, если один из участников по неосторожности ``выпустит информацию из рук'' преждевременно, то в обмен он может получить совсем не то, проблемы здесь те же, что и в ``протоколе'' обмена расписки на ассигнации у Чичикова и Собакевича. Из всех криптографических протоколов данного типа, пожалуй, наиболее наглядным, и к тому же достаточно простым, является протокол подбрасывания монеты. Предположим, что двум участникам, Алисе и Бобу, необходимо бросить жребий. В случае, когда они оба физически находятся в одном и том же месте, задачу можно решить с помощью обычной процедуры подбрасывания монеты. Если кто-либо из участников не доверяет монете, можно использовать другие источники случайности. Правда, создание надежных источников случайности - весьма непростая задача, но она уже относится к математической статистике, а не к криптографии. Если же Алиса и Боб удалены друг от друга и могут общаться лишь по каналу связи, то задача о жребии, на первый взгляд, кажется неразрешимой. В самом деле, если, следуя обычной процедуре подбрасывания монеты, первый ход делает Алиса, которая выбирает один из возможных вариантов - ``орел'' или ``решка'', то Боб всегда может объявить тот исход, который ему выгоден. Тем не менее, эта задача была решена Блюмом [14]. Любопытно, что даже в заголовке своей работы Блюм охарактеризовал предложенный им метод как метод ``решения нерешаемых задач''.
Легко понять, что задача о жребии решается очень просто,
если существует надежный агент - третья сторона, которая
пользуется полным доверием и Алисы, и Боба, и которая имеет
конфиденциальные (закрытые) каналы связи с обоими
участниками. В этом случае Боб и Алиса выбирают случайные
биты
В отсутствие надежного агента срабатывает идея, которую
проще всего понять на следующей ``физической'' реализации.
Боб выбирает случайный бит Ниже мы излагаем криптографическую реализацию той же идеи, основанную на задаче дискретного логарифмирования, и используем при этом обозначения из раздела 3.
Протокол подбрасывания монеты
![]() ![]() ![]() ![]()
![]() ![]() ![]() ![]() ![]()
![]()
![]() ![]()
![]() ![]()
Значение
С другой стороны, Боб может обманывать, т.е. открывать
значение бита
![]() ![]()
![]() ![]()
![]() ![]()
![]() ![]() ![]() ![]()
![]() ![]() ![]() ![]() ![]()
На основе этих соображений можно построить доказательство
следующего утверждения: в предположении трудности задачи
дискретного логарифмирования приведенный выше протокол
подбрасывания монеты является стойким. Заметим, что для
данного протокола достаточно весьма слабой формы этого
предположения. Поскольку Алиса может прекратить выполнение
протокола, если с момента передачи значения
Если из приведенного выше
протокола подбрасывания монеты
вычленить шаги 1, 2 и 4, то получим так называемый протокол
привязки к биту (bit commitment). Шаги 1 и 2 в таком
протоколе называются этапом привязки, а шаг 4 - этапом
открытия бита. В этом протоколе для значения 1) после выполнения этапа привязки получатель не может самостоятельно определить, какой бит упакован в блоб; 2) на этапе открытия бита отправитель может открыть любой блоб либо только как 0, либо только как 1. В нашем случае требование 1) выполняется безусловно, т.е. вне зависимости от того, какими вычислительными ресурсами обладает получатель, он не может самостоятельно узнать, какой бит находится в блобе. В таких случаях говорят, что протокол гарантирует безусловную безопасность отправителя. В то же время безопасность получателя основывается на недоказанном предположении о вычислительной трудности задачи дискретного логарифмирования. Такая асимметрия типична для многих типов криптографических протоколов. Она имеется, например, в доказательствах с вычислительно нулевым разглашением. Но существует и другой тип протоколов привязки к биту, в которых уже безопасность получателя безусловна, а безопасность отправителя основывается на недоказанных предположениях. Для многих типов криптографических протоколов с указанной выше асимметрией построены такого рода двойственные протоколы.
Протокол привязки к биту - один из основных типов
примитивных криптографических протоколов. Он находит
многочисленные применения в криптографии. В качестве
иллюстрации рассмотрим способ повышения эффективности
доказательств с нулевым разглашением на примере
рассмотренного в главе 2 протокола для задачи ИЗОМОРФИЗМ
ГРАФОВ. В этом протоколе главная
проблема - большое количество раундов, растущее
пропорционально размеру графа. Достаточно естественная
идея - выполнить все эти последовательные раунды
параллельно. На первом шаге P выбирает
Но будет ли такой протокол доказательством с нулевым
разглашением? Прежде всего заметим, что этот протокол
трехраундовый, а как показывает уже упоминавшийся в разделе 3
результат Гольдрайха и Кравчика, трехраундовых
доказательств с нулевым разглашением скорее всего не
существует. Тот метод, который использовался в главе 2 для
построения моделирующей машины, срабатывал, поскольку при
последовательном выполнении протокола моделирующая машина
могла угадать на каждом раунде запрос
Зависимость
В результате количество раундов в протоколе возросло, но
осталось константой (достаточно 5 раундов). При
использовании протокола привязки к биту, обеспечивающего
безусловную безопасность отправителя, даже обладающий
неограниченными вычислительными возможностями доказывающий
не может извлечь из блобов
Итак, второе из указанных выше препятствий устранено. А как
быть с первым? Оказывается, моделирующей машине совсем
необязательно угадывать запросы V
Предположим, что то предположение, на котором основывается
стойкость протокола привязки к биту, стало доказанным
фактом. Например, удалось доказать, что не существует
полиномиальных алгоритмов для задачи дискретного
логарифмирования. Даже в этом случае полиномиально
ограниченный отправитель в приведенном выше протоколе
привязки к биту может угадать
Next: 3.5. Еще раз о Up: 3. Криптографические протоколы Previous: 3.3. Неотслеживаемость. Электронные деньги Contents: Содержание |
![]() ![]() |