Все о геологии :: на главную страницу! Геовикипедия 
wiki.web.ru 
Поиск  
   Rambler's Top100 Service
 Главная страница  Конференции: Календарь / Материалы  Каталог ссылок    Словарь       Форумы        В помощь студенту     Последние поступления
   Геология | Книги
 Обсудить в форуме  Добавить новое сообщение
Next: 3.5. Еще раз о Up: 3. Криптографические протоколы Previous: 3.3. Неотслеживаемость. Электронные деньги Contents: Содержание


3.4. Протоколы типа ``подбрасывание монеты по телефону''

``- Хорошо, дайте же сюда деньги.
- На что-ж деньги? У меня вот они в руке! Как только напишете расписку, в ту же минуту их возьмете.
- Да позвольте, как же мне писать расписку? Прежде нужно видеть деньги.
Чичиков выпустил из рук бумажки Собакевичу, который, приблизившись к столу и накрывши их пальцами левой руки, другою написал на лоскутке бумаги, что задаток двадцать пять рублей государственными ассигнациями за проданные души получен сполна.''

Н. В. Гоголь. ``Мертвые души'', глава 5.

В данном разделе мы кратко обсудим те типы криптографических протоколов, в которых два участника должны обменяться некоторой информацией. Но участники не доверяют друг другу и каждый из них может оказаться обманщиком. Поэтому, если один из участников по неосторожности ``выпустит информацию из рук'' преждевременно, то в обмен он может получить совсем не то, проблемы здесь те же, что и в ``протоколе'' обмена расписки на ассигнации у Чичикова и Собакевича.

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

Если же Алиса и Боб удалены друг от друга и могут общаться лишь по каналу связи, то задача о жребии, на первый взгляд, кажется неразрешимой. В самом деле, если, следуя обычной процедуре подбрасывания монеты, первый ход делает Алиса, которая выбирает один из возможных вариантов - ``орел'' или ``решка'', то Боб всегда может объявить тот исход, который ему выгоден.

Тем не менее, эта задача была решена Блюмом [14]. Любопытно, что даже в заголовке своей работы Блюм охарактеризовал предложенный им метод как метод ``решения нерешаемых задач''.

Легко понять, что задача о жребии решается очень просто, если существует надежный агент - третья сторона, которая пользуется полным доверием и Алисы, и Боба, и которая имеет конфиденциальные (закрытые) каналы связи с обоими участниками. В этом случае Боб и Алиса выбирают случайные биты $ b$ и $ c$ соответственно и посылают их в тайне друг от друга агенту. Последний ждет, пока не поступят оба бита, и после этого публикует $ b$, $ c$ и $ d=b\oplus c$ - исход подбрасывания монеты.

В отсутствие надежного агента срабатывает идея, которую проще всего понять на следующей ``физической'' реализации. Боб выбирает случайный бит $ b$, записывает его на листе бумаги, запирает этот лист в ящике, оставляя ключ от замка у себя, и посылает ящик Алисе. Предполагается, что, не имея ключа, Алиса не может добраться до содержимого ящика. Получив ящик, Алиса выбирает случайный бит $ c$ и посылает его Бобу. В ответ Боб посылает Алисе ключ от ящика. Исходом подбрасывания монеты будет опять-таки бит $ d=b\oplus c$.

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


Протокол подбрасывания монеты

  • Алиса выбирает случайное число $ x$ из $ Z_q$, вычисляет $ y=g^x\nmod p$ и посылает $ y$ Бобу.

  • Боб выбирает случайный бит $ b$, случайное число $ k$ из $ Z_q$, вычисляет $ r=y^bg^k\nmod p$ и посылает $ r$ Алисе.

  • Алиса выбирает случайный бит $ c$ и посылает его Бобу.

  • Боб посылает Алисе $ b$ и $ k$.

  • Алиса проверяет, выполняется ли сравнение $ r=y^bg^k\pmod p$. Если да, то результатом выполнения протокола будет бит $ d=b\oplus c$.


    • Значение $ r$ - это криптографический аналог того ящика, о котором шла речь в описании физической реализации. В самом деле, из значения $ r$ Алиса не может извлечь никакой информации о бите $ b$. Поскольку $ k$ выбирается случайным образом из $ Z_q$, значение $ r$ в обоих случаях, при $ b=0$ и $ b=1$, является случайным элементом группы, порожденной $ g$, и поэтому не несет никакой информации о значении бита $ b$ (разумеется, Алиса может попытаться обманывать, выбирая значение $ y$, не принадлежащее группе, порожденной $ g$; однако Боб легко обнаружит такой обман, проверяя сравнение $ y^q=1\pmod p$).

    С другой стороны, Боб может обманывать, т.е. открывать значение бита $ b$ по своему желанию и как 0, и как 1, но только в том случае, если он умеет вычислять дискретные логарифмы. Это вытекает из следующих соображений. Поскольку, как уже отмечалось выше, можно считать, что значение $ r$ заведомо принадлежит группе, порожденной $ g$, существует единственное число $ \alpha \in Z_q$ такое, что $ r=g^\alpha \pmod p$. Для того, чтобы открыть значение $ b=0$, Боб должен послать Алисе на шаге 4 число $ \alpha$, а для того, чтобы открыть значение $ b=1$, - число $ k=(\alpha -x)\nmod q$. Отсюда $ x=(\alpha -k)\nmod q$. Пусть $ M$ - полиномиальная вероятностная машина Тьюринга, которую Боб использует для осуществления такого обмана. Тогда следующий алгоритм будет вычислять дискретные логарифмы.

  • Передаем входное значение $ y$ машине $ M$.

  • Получив в ответ значение $ r$, запоминаем состояние машины $ M$.

  • Выбираем случайный бит $ c$ и передаем его $ M$.

  • Получив от $ M$ значения $ b$ и $ k$, запоминаем эти величины, восстанавливаем ранее запомненное состояние машины $ M$ и переходим на шаг 3.

  • Как только среди пар $ (b,k)$ найдутся $ (0,k_1)$ и $ (1,k_2)$, вычисляем $ x=(k_1-k_2)\nmod q$ - дискретный логарифм величины $ y$.

    • На основе этих соображений можно построить доказательство следующего утверждения: в предположении трудности задачи дискретного логарифмирования приведенный выше протокол подбрасывания монеты является стойким. Заметим, что для данного протокола достаточно весьма слабой формы этого предположения. Поскольку Алиса может прекратить выполнение протокола, если с момента передачи значения $ y$ Бобу до момента получения от него значений $ b$ и $ k$ проходит более, скажем, 30 секунд, достаточно предположить, что задача дискретного логарифмирования не может быть решена за такое время.

    Если из приведенного выше протокола подбрасывания монеты вычленить шаги 1, 2 и 4, то получим так называемый протокол привязки к биту (bit commitment). Шаги 1 и 2 в таком протоколе называются этапом привязки, а шаг 4 - этапом открытия бита. В этом протоколе для значения $ r$, в которое упаковывается бит $ b$, (аналог ящика в физической реализации) обычно используется термин блоб (blob), для Алисы - получатель, а для Боба - отправитель. Говоря неформально, от протокола привязки к биту требуется такая конструкция блоба, которая обеспечивает одновременное выполнение следующих двух требований:

    1) после выполнения этапа привязки получатель не может самостоятельно определить, какой бит упакован в блоб;

    2) на этапе открытия бита отправитель может открыть любой блоб либо только как 0, либо только как 1.

    В нашем случае требование 1) выполняется безусловно, т.е. вне зависимости от того, какими вычислительными ресурсами обладает получатель, он не может самостоятельно узнать, какой бит находится в блобе. В таких случаях говорят, что протокол гарантирует безусловную безопасность отправителя. В то же время безопасность получателя основывается на недоказанном предположении о вычислительной трудности задачи дискретного логарифмирования. Такая асимметрия типична для многих типов криптографических протоколов. Она имеется, например, в доказательствах с вычислительно нулевым разглашением. Но существует и другой тип протоколов привязки к биту, в которых уже безопасность получателя безусловна, а безопасность отправителя основывается на недоказанных предположениях. Для многих типов криптографических протоколов с указанной выше асимметрией построены такого рода двойственные протоколы.

    Протокол привязки к биту - один из основных типов примитивных криптографических протоколов. Он находит многочисленные применения в криптографии. В качестве иллюстрации рассмотрим способ повышения эффективности доказательств с нулевым разглашением на примере рассмотренного в главе 2 протокола для задачи ИЗОМОРФИЗМ ГРАФОВ. В этом протоколе главная проблема - большое количество раундов, растущее пропорционально размеру графа. Достаточно естественная идея - выполнить все эти последовательные раунды параллельно. На первом шаге P выбирает $ m$ случайных перестановок $ \pi _1,\dots ,\pi _m$, вычисляет $ H_1=\pi _1G_1,\dots ,H_m=\pi _mG_1$ и посылает все эти $ m$ графов V. На втором шаге V выбирает $ m$ случайных битов $ \alpha _1,\dots ,\alpha _m$ и посылает их P, а на третьем P формирует все $ m$ требуемых перестановок и посылает их V.

    Но будет ли такой протокол доказательством с нулевым разглашением? Прежде всего заметим, что этот протокол трехраундовый, а как показывает уже упоминавшийся в разделе 3 результат Гольдрайха и Кравчика, трехраундовых доказательств с нулевым разглашением скорее всего не существует. Тот метод, который использовался в главе 2 для построения моделирующей машины, срабатывал, поскольку при последовательном выполнении протокола моделирующая машина могла угадать на каждом раунде запрос $ \alpha _i$ проверяющего с вероятностью $ 1/2$. В параллельном же варианте вероятность угадывания равна $ 1/{2^m}$, т.е. пренебрежимо мала. Кроме того, проверяющий формирует свои запросы $ \alpha _1,\dots ,\alpha _m$, уже получив от P все графы $ H_1,\dots ,H_m$, и может выбирать их (запросы) зависящими достаточно сложным образом от всех этих графов. Это также представляется непреодолимым препятствием при попытке построения моделирующей машины.

    Зависимость $ \alpha _1,\dots ,\alpha _m$ от $ H_1,\dots ,H_m$ можно предотвратить следующим образом. Проверяющий V выбирает свои запросы в самом начале выполнения протокола, еще до того, как увидит $ H_1,\dots ,H_m$. Каждый бит $ \alpha _i$ упаковывается в блоб $ r_i$, и V посылает все блобы $ r_1,\dots ,r_m$ доказывающему. Только после этого P посылает V все графы $ H_1,\dots ,H_m$. В ответ V открывает блобы, а P, получив $ \alpha _1,\dots ,\alpha _m$, формирует требуемые перестановки и посылает их V.

    В результате количество раундов в протоколе возросло, но осталось константой (достаточно 5 раундов). При использовании протокола привязки к биту, обеспечивающего безусловную безопасность отправителя, даже обладающий неограниченными вычислительными возможностями доказывающий не может извлечь из блобов $ r_1,\dots ,r_m$ никакой информации о запросах $ \alpha _1,\dots ,\alpha _m$. Поэтому корректность протокола сохраняется.

    Итак, второе из указанных выше препятствий устранено. А как быть с первым? Оказывается, моделирующей машине совсем необязательно угадывать запросы V$ ^*$. Следующая замечательная идея многократно использовалась в работах, посвященных криптографическим протоколам (см. [15]). Моделирующая машина $ M_{V^*}$, получив от V$ ^*$ блобы, запоминает состояние машины V$ ^*$, выбирает графы $ H'_1,\dots ,H'_m$, как случайные перестановки графа $ G_0$, и передает их V$ ^*$. В ответ V$ ^*$ открывает блобы, и $ M_{V^*}$ получает запросы $ \alpha _1,\dots ,\alpha _m$. После этого моделирующая машина формирует графы $ H_1,\dots ,H_m$ как ответы на запросы $ \alpha _1,\dots ,\alpha _m$, восстанавливает запомненное состояние машины V$ ^*$ и передает ей $ H_1,\dots ,H_m$. Поскольку протокол привязки к биту предполагается стойким, машина $ M_{V^*}$ вновь получит те же самые биты $ \alpha _1,\dots ,\alpha _m$ и успешно завершит моделирование, выдавая $ \alpha _1,\dots ,\alpha _m$, $ H_1,\dots ,H_m$, требуемые перестановки, а также блобы $ r_1,\dots ,r_m$ и те сообщения, которые были выданы машиной V$ ^*$ для их открытия.

    Предположим, что то предположение, на котором основывается стойкость протокола привязки к биту, стало доказанным фактом. Например, удалось доказать, что не существует полиномиальных алгоритмов для задачи дискретного логарифмирования. Даже в этом случае полиномиально ограниченный отправитель в приведенном выше протоколе привязки к биту может угадать $ x$ хоть и с малой, но ненулевой вероятностью, и обмануть получателя. Из-за этого рассмотренный нами параллельный вариант протокола будет доказательством лишь со статистически нулевым разглашением. А исходный последовательный вариант (см. главу 2) обладал свойством абсолютно нулевого разглашения. В работе Беллара, Микали и Островски [15], где был предложен описанный выше способ преобразования последовательных протоколов в параллельные, используется специальная конструкция блобов для задачи ИЗОМОРФИЗМ ГРАФОВ, сохраняющая свойство абсолютно нулевого разглашения.

    Next: 3.5. Еще раз о Up: 3. Криптографические протоколы Previous: 3.3. Неотслеживаемость. Электронные деньги Contents: Содержание

    Проект осуществляется при поддержке:
     Геологического факультета МГУ,
    РФФИ
    		    
    TopList Rambler's Top100