Все о геологии :: на главную страницу! Геовикипедия 
wiki.web.ru 
Поиск  
   Rambler's Top100 Service
 Главная страница  Конференции: Календарь / Материалы  Каталог ссылок    Словарь       Форумы        В помощь студенту     Последние поступления
   Геология | Курсы лекций
 Обсудить в форуме  Добавить новое сообщение
Вперед Вверх Назад Содержание Предметный указатель
Вперед: Литература Вверх: 15. Основные понятия теории доказательств с нулевым разглашением Назад: 15.2 Интерактивные системы доказательства   Содержание   Предметный указатель


15.3 Интерактивные системы доказательства с нулевым разглашением

Предположим, что задана интерактивная система $ \langle V,P\rangle $, где игрок $ P$ доказывает игроку $ V$ истинность утверждения $ S$, состоящего, например, в том, что некоторые графы $ G_{0}$ и $ G_{1}$ изоморфны. Для достижения своей цели игрок $ P$ может просто предъявить игроку $ V$ изоморфизм между $ G_{0}$ и $ G_{1}$, который игрок $ V$ самостоятельно вычислить не в состоянии и хотел бы получить от игрока $ P$. Предположим однако, что предоставление игроку $ V$ столь исчерпывающей информации не в интересах игрока $ P$ и он хотел бы сохранить ее в секрете. Таким образом, цель игрока $ P$ -- убедить игрока $ V$, что заданные графы изоморфны, не выдав при этом никаких полезных сведений, которые игрок $ V$ не мог бы получить самостоятельно. Более того, мы хотим, чтобы эта цель достигалась даже если игрок $ P$ имеет дело с любым другим игроком $ V'$ (с полиномиально ограниченными возможностями), задавшимся целью получить от $ P$ как можно больше сведений. Оказывается, можно разработать протокол $ \langle V,P\rangle $, являющийся интерактивным доказательством в смысле определения из раздела 15.2 и дополнительно учитывающий эти специфические интересы игрока $ P$. В случае, если графы $ G_{0}$ и $ G_{1}$ действительно изоморфны, игрок $ V$ (и даже любой "злоумышленник" $ V'$ с произвольной полиномиально ограниченной вероятностной стратегией, вступивший в игру с игроком $ P$ вместо $ V$) не получит от игрока $ P$ никакой дополнительной информации в том смысле, что вся ставшая доступной ему в результате игры информация (а именно, последовательность результатов подбрасываний собственной монеты, собственных сообщений и сообщений игрока $ P$) является случайной величиной (зависящей от подбрасываний монет игроками $ V$ и $ P$), которая может быть промоделирована некоторым вероятностным полиномиальным алгоритмом. Следовательно, игрок $ V$ и без участия игрока $ P$ мог бы с помощью этого алгоритма получить эту информацию. Заметим однако, что упомянутый моделирующий алгоритм сам по себе не пригоден для решения вопроса, изоморфны ли графы $ G_{0}$ и $ G_{1}$ (этот аспект более подробно обсуждается ниже).

Такая система доказательства $ \langle V,P\rangle $ называется системой доказательства с нулевым разглашением. В качестве примера ниже дается описание соответствующего протокола для языка ИЗОМОРФИЗМ ГРАФОВ (GRAPH ISOMORPHISM, сокращенно GI), состоящего из всех пар $ G_{0}$ и $ G_{1}$ изоморфных графов ([GMW2]). Предполагаем, что графы $ G_{0}$ и $ G_{1}$ заданы на одном и том же множестве вершин $ N$, $ \vert N\vert=m$, и что $ \varphi$ -- перестановка вершин $ N$, являющаяся изоморфизмом графов $ G_{0}$ и $ G_{1}$, что мы запишем как $ G_{1}=\varphi G_{0}$.

Следующий протокол повторяется последовательно $ m$ раз:

    $ P$: выбирает случайную перестановку вершин $ \pi$ и вычисляет $ H=\pi G_{1}$;

    $ P\longrightarrow V$: $ H$;

    $ V$: выбирает случайный бит $ \alpha $;

    $ V\longrightarrow P$: $ \alpha $;

    $ P\longrightarrow V$: $ \psi=\begin{cases} \pi,&\text{если }\alpha =1,\\ \pi\circ\varphi,&\text{если }\alpha\ne1; \end{cases}$

    $ V$: если $ H\ne\psi G_{\alpha }$, то останавливается и выдает отрицательный ответ. Если это равенство ни разу не было нарушено, то игрок V дает окончательный положительный ответ.

Изложенный протокол является интерактивным доказательством для GI. Действительно, игрок $ P$ предъявляет граф $ H$, изоморфный $ G_{1}$, а игрок $ V$ требует доказать изоморфность $ H$ либо $ G_{0}$, либо $ G_{1}$. Если $ G_{0}$ и $ G_{1}$ изоморфны, то это возможно с вероятностью 1, если графы неизоморфны, то это возможно лишь с вероятностью $ 1/2$ в каждом вызове протокола и с вероятностью $ 1/2^{m}$ во всех $ m$ вызовах. Этот протокол является протоколом с нулевым разглашением, так как в случае изоморфных $ G_{0}$ и $ G_{1}$ игрок $ V$ не получает никакой информации, кроме изоморфизмов графов $ G_{0}$ и $ G_{1}$ с какими-то их случайными перенумерациями, которые он мог бы получить и самостоятельно, просто-напросто выбирая случайные $ \alpha $ и перенумеровывая случайным образом граф $ G_{\alpha }$.

Перейдем теперь к формальным определениям, введенным в работе Гольдвассер, Микали и Ракоффа [GMR1].

Пусть для каждого фиксированного слова $ x$ $ A(x)$ и $ B(x)$ -- это случайные величины, значения которых являются двоичными словами. Семейства случайных величин $ \{A(x)\}$ и $ \{B(x)\}$ называются статистически неразличимыми (statistically indistinguishable) на множестве $ X$, если

$\displaystyle \sum_{s\in \{0,1\}*} \vert\Pr[A(x)=s]-\Pr[B(x)=s]\vert < \vert x\vert^{-c} $

для любой константы $ c>0$ и всех достаточно длинных $ x\in X$.

Пусть $ C_{n}$ для $ n\in\mathbb{N}$ -- это булева схема (т. е. схема, собранная из элементов $ \neg,\wedge,\vee$, которая при каждой подстановке значений 0 и 1 вместо входных переменных позволяет получить на выходе значение 0 или 1). Запись $ C_{n}(s)=1$ будет означать, что на входном слове $ s$ схема $ C_{n}$ выдает значение 1. Семейство $ \{C_{n}\}$ называется полиномиально ограниченным, если для некоторой константы $ d$ и всех достаточно больших $ n$ количество функциональных элементов в схеме $ C_{n}$ не превосходит $ n^{d}$. Семейства случайных величин $ \{A(x)\}$ и $ \{B(x)\}$ называются вычислительно неразличимыми (computationally indistinguishable) на множестве $ X$, если для произвольного полиномиально ограниченного семейства схем $ \{C_{n}\}$

$\displaystyle \vert\Pr[C_{\vert x\vert}(A(x))=1]-\Pr[C_{\vert x\vert}(B(x))=1]\vert < \vert x\vert^{-c} $

для любой константы $ c$ и всех достаточно длинных $ x\in X$. Предполагается, что случайные величины $ \{A(x)\}$ и $ \{B(x)\}$ принимают значения, длина которых совпадает с количеством входных переменных схемы $ C_{\vert x\vert}$.

Легко видеть, что если семейства случайных величин статистически неразличимы, то они и вычислительно неразличимы.

Рассмотрим интерактивную систему $ \langle V,P\rangle $. Внесем в определение раздела 15.2 следующее дополнение. Пусть $ V$ обладает дополнительной входной лентой, на которой записано дополнительное входное слово $ h$ (что соответствует ситуации, когда игрок $ V$ получил где-то какую-то дополнительную информацию или запомнил сообщения, которые он получал в предыдущих вызовах протокола). В результате выполнения протокола на входе $ (w,h)$ игрок $ V$ получает следующую информацию: результаты подбрасываний своей монеты $ r$, последовательность $ u_{i}$ своих сообщений и ответов $ v_{i}$ на них игрока $ P$, $ i\leqslant k$. Обозначим последовательность $ (r,u_{1},v_{1},\ldots ,u_{k},v_{k})$ через $ \qopname\relax o{view}_{\scriptscriptstyle V,P}(w,h)$ и будем рассматривать ее как случайную величину, значение которой определяется подбрасываниями монет игроками $ V$ и $ P$.

Пусть $ M$ -- вероятностная машина Тьюринга, результатом вычисления которой являются слова (произвольной длины), зависящие от содержимого ее случайной ленты. Таким образом, результат вычисления $ M$ на входном слове $ x$ -- это случайная величина, которую мы будем обозначать через $ M(x)$, зависящая от случайной строки машины $ M$. Время работы машины $ M$ на входе $ x$ тоже зависит от полученной ею случайной строки. Если его математическое ожидание ограничено полиномом от длины $ x$, то говорим, что $ M$ работает за полиномиальное в среднем время.

Система $ \langle V,P\rangle $ называется интерактивной системой доказательства с нулевым разглашением для языка $ L$ (zero-knowledge interactive proof system, иногда computationally zero-knowledge, т. е., системой доказательства с вычислительно нулевым разглашением), если она является интерактивной системой доказательства для $ L$, т. е. выполнены условия 1 и 2 из раздела 15.2 (при любом $ h$) и, кроме этого, выполняется следующее условие:     3) для любой полиномиальной вероятностной машины Тьюринга $ V'$ существует вероятностная машина Тьюринга $ M_{V'}$, работающая за полиномиальное в среднем время и такая, что семейства случайных величин $ \qopname\relax o{view}_{\scriptscriptstyle V',P}(w,h)$ и $ M_{V'}(w,h)$ вычислительно неразличимы на множестве $ \{(w,h):w\in L\}$.

Система $ \langle V,P\rangle $ называется интерактивной системой доказательства для $ L$ со статистически нулевым разглашением (statistically zero-knowledge, иногда almost-perfectly zero-knowledge), если усилить требование вычислительной неразличимости до статистической неразличимости. Система $ \langle V,P\rangle $ называется интерактивной системой доказательства для $ L$ с абсолютно нулевым разглашением (perfect zero-knowledge), если потребовать, чтобы семейства случайных величин $ \qopname\relax o{view}_{\scriptscriptstyle V',P}(w,h)$ и $ M_{V'}(w,h)$ совпадали.

Языки, обладающие доказательствами с (абсолютно, статистически) нулевым разглашением, образуют класс (PZK, SZK или иногда APZK) ZK. Очевидными являются включения

   BPP$\displaystyle {}\subseteq{}$PZK$\displaystyle {}\subseteq{}$SZK$\displaystyle {}\subseteq{}$   ZK$\displaystyle {}\subseteq{}$IP$\displaystyle .$

Приведенная выше интерактивная система доказательства для языка GI является системой с абсолютно нулевым разглашением.


Замечания

1. Из определения величины $ \qopname\relax o{view}_{\scriptscriptstyle V,P}(w,h)$ без всякого ущерба можно исключить сообщения $ u_{i}$, $ i\leqslant k$, игрока $ V$ игроку $ P$, так как они однозначно определяются полиномиальным алгоритмом исходя из последовательности $ (r,v_{1},\ldots ,v_{k})$.

2. Поскольку время работы машины $ V'$ ограничено некоторым полиномом, можно считать, что длина дополнительного входного слова $ h$ ограничена тем же полиномом (своим для каждой машины $ V'$). Орен [Ore], который предложил эту модификацию определения, никаких ограничений на $ h$ не накладывал. Выше было объяснено, какой смысл имеет предоставление игроку $ V$ дополнительного входного слова $ h$. Важной мотивацией этого является и то обстоятельство, что без такой модификации определения интерактивной системы не имеет места следующий факт (см. [GKr]). Последовательное выполнение двух протоколов с нулевым разглашением является протоколом с нулевым разглашением. С другой стороны, читателю, обратившемуся к данному подразделу с целью получения общего представления о понятии доказательства с нулевым разглашением и не интересующемуся вопросами композиции протоколов, рекомендуется упростить данное определение, опустив все упоминания о слове $ h$.

3. Гольдрайх и Кравчик показали [GKr], что параллельное выполнение протоколов с нулевым разглашением не обязательно приводит к протоколам с нулевым разглашением (сравнить с замечанием 4 раздела 15.2).

4. В определении для любого возможного игрока $ V'$ мы требуем существования своей моделирующей машины $ M_{V'}$. Назовем систему с нулевым разглашением системой с универсальной моделирующей машиной (black-box zero-knowledge), если существует вероятностная машина $ M$, работающая за полиномиальное в среднем время, которая является моделирующей машиной для любого $ V'$ и пользуется программой $ V'$ как "черным ящиком". Все до сих пор известные системы с нулевым разглашением являются системами с универсальными моделирующими машинами. Вопрос о существовании систем, не обладающих таким свойством, остается открытым.

5. Доказательства с нулевым разглашением тривиальным образом существуют для всех языков из класса BPP: поскольку игрок $ V$ может сам выяснить принадлежность языку любого данного слова, диалог с игроком $ P$ заведомо не дает ему никакой дополнительной информации. Поэтому, доказательства с нулевым разглашением являются нетривиальным объектом только при некоторых теоретико-сложностных предположениях, таких как P$ {}\neq{}$NP.

6. Определение доказательства с нулевым разглашением, на первый взгляд, может показаться парадоксальным. В самом деле, корректность протокола означает, что никакой "злоумышленник" не имеет достойных внимания шансов обмануть игрока $ V$, и в то же время из свойства нулевого разглашения следует существование полиномиальной моделирующей машины, которая достаточно точно имитирует распределение случайных величин, возникающих в процессе выполнения протокола. Почему бы "злоумышленнику" не воспользоваться этой машиной? Для разрешения этого кажущегося противоречия следует уяснить следующие два момента. Во-первых, моделирующая машина может "воспроизвести" только информацию, которую игрок $ V$ получает в процессе выполнения протокола, но не сам протокол. Так, для приведенного выше примера моделирующая машина может строить случайные перенумерации исходных графов $ G_{0}$ и $ G_{1}$, но не может, если ей неизвестен изоморфизм между этими графами, адекватным образом ответить на запрос игрока $ V$, задаваемый случайным битом $ \alpha $. Во-вторых, определение доказательства с нулевым разглашением описывает поведение моделирующей машины только на входных словах, принадлежащих данному языку. На остальных словах эта машина может делать все что угодно. Поэтому моделирующая машина, с помощью которой устанавливается свойство нулевого разглашения некоторого протокола доказательства для данного языка, не может использоваться для распознавания этого языка (если только этот язык не принадлежит классу BPP).


Следующая теорема была доказана Гольдрайхом, Микали и Вигдерсоном [GMW1] (окончательная версия [GMW2]).

Теорема 2.  Если существует односторонняя перестановка (см. определение ниже), то всякий язык из класса NP обладает доказательством с нулевым разглашением, т. е. NP $ {}\subseteq{}$ZK.

Определение.  Взаимно однозначная и сохраняющая длину функция $ f\colon\{0,1\}^{n}\to\{0,1\}^{n}$, $ n\in\mathbb{N}$, называется односторонней перестановкой ((strong non-uniformly) one-way permutation), если она вычислима за полиномиальное время и для любого полиномиально ограниченного семейства булевых схем $ C_{n}$ (с $ n$ выходами) для произвольной константы $ c>0$ при достаточно больших $ n$

$\displaystyle \Pr\left[C_{n}(x)=f^{-1}(x)\right]<1/n^{c}, $

где вероятность берется по $ x$, равномерно распределенным на $ \{0,1\}^{n}$.

Обобщение изложенного результата было получено Бен-Ором и др. [Betal].

Теорема 3.  При условии существования односторонней перестановки IP$ {}={}$ZK, т. е. все, что может быть доказано интерактивной системой, может быть доказано с нулевым разглашением.

Следствие.  При условии существования односторонней перестановки ZK$ {}={}$PSPACE.

Замечание.  Утверждение о том, что теорема 3 верна и при более слабом предположении о существовании односторонней функции стало уже частью своеобразного "криптографического фольклора": оно упоминается в нескольких работах (см., например, [FKLN]). Однако, нам неизвестно, опубликовано ли где-нибудь доказательство этого результата.

Естественно возникает вопрос, насколько существенным в приведенных выше результатах является предположение о существовании односторонней функции. Островски и Вигдерсон [OWi] доказали, что если не существует односторонних функций (в смысле несколько ослабленного определения), то доказательствами с нулевым разглашением обладают только языки из класса BPP.

Вперед Вверх Назад Содержание Предметный указатель
Вперед: Литература Вверх: 15. Основные понятия теории доказательств с нулевым разглашением Назад: 15.2 Интерактивные системы доказательства   Содержание   Предметный указатель

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