\documentclass{article}
\usepackage{amssymb}
\usepackage{amsmath}

\newcommand{\prover}{\textsc{\textbf{P}}}
\newcommand{\verifier}{\textsc{\textbf{V}}}
\newcommand{\verifierst}{\textbf{\textsf{V'}}}

\title{Введение в нулевое разглашение, 18.10.2005}
\author{Ю. Лифшиц\thanks{Законспектировал П. Никитин.}.}

\begin{document}
\maketitle

\section*{План лекции}
\begin{enumerate}
\item Интерактивные доказательства, языки
\item Примеры интерактивных доказательств
\item Нулевое разглашение (Определение, доказательство)
\item Задачи для самостоятельного решения
\end{enumerate}
\par

\section{Интерактивные доказательства, языки}
\subsection{Введение}
Нулевое разглашение является одним из главных достижений современной теоретической
информатики в целом (не только криптографии) за по\-след\-ние 20 лет и имеет очень много
приложений -- как теоретических, так и кон\-крет\-ных практических. Эта лекция -- вводная,
на ней мы познакомимся с нулевым разглашением, как со свойством интерактивного доказательства.\par
Неформально, интерактивное доказательство -- диалог двух лиц, одно из которых проверяет
доказательство (в дальнейшем -- \verifier\ или \verifier erifier), а другое пытается убедить
первого в том, что действительно знает до\-каза\-тель\-ство (в дальнейшем -- \prover\ или
\prover rover).

\subsection{Обычные доказательства}
Обычное доказательство мы будем рассматривать в понимании Дэвида Гильберта,
(книга "Основания Геометрии").\par
Вначале задаётся базовый список {\it аксиом}, на которые мы опираемся (или определений).
Есть {\it правила вывода} (например индукция, до\-каза\-тель\-ство от противного, и т. д.), и
мы строим до\-каза\-тель\-ство, как список утверждений -- от условия задачи (и аксиом) к
утверждению задачи.

\subsection{Понятие языка}
Понятие языка является основным в теории сложности. Язык -- это набор $L$ строк конечной
длины $n$ из нулей и единиц, т. е. $L \subset \bigcup_{x_i \in \{0,\ 1\}^n} x_i$, где
$1 \leqslant i \leqslant 2^n;$ вот некоторые примеры:
\begin{itemize}
\item Все строки только из нулей.
\item Все строки, в кототрых нулей и единиц поровну.
\item Все строки вообще
\end{itemize}
Языков много, но мы остановимся на только одном из них подробно и умомянем ещё более
общий по сравнению с ним.

\subsection{Языки NP-класса}
Язык $L$ принадлежит NP, если существует полиномиальный алгоритм $P$, такой что
$x\in L \Leftrightarrow \exists y : P(x,y)=1,$ т. е. алгоритм проверки при\-над\-леж\-но\-сти $x$
к языку $L$ по подсказке $y$. Тогда для $x\in L$ значение такого $y$, что $P(x,y)=1$,
является ``доказательством'' принадлежности языку. Заметим, что $y$ должен быть
полиномиального размера от $x$, иначе $P$ даже не успел бы прочитать подсказку.\par
Примеры:
\begin{itemize}
\item Составные числа. Подсказка -- два нетривиальных простых мно\-жи\-те\-ля в его разложении.
Алгоритм $P$ -- перемножение этих чисел.
\item Язык, содержащий пары изоморфных графов. Тогда подсказка для проверки принадлежности
этой пары к языку -- просто явно заданный изоморфизм.
\end{itemize}
Кроме того, существует язык $PSPACE$, который определяется так же, как $NP$, но с
ограничением на память, используемую алгоритмом $P$. Т.е. $PSPACE$ -- класс языков, такой
что Язык $L$ принадлежит $PSPACE$, если существует алгоритм $P$, использующий
полиномиальный объем памяти, такой что $x\in L \Leftrightarrow P(x)=1$.

\subsection{Интерактивные доказательства}
Давайте опишем связь между языками и задачами. {\it Массовая задача} -- набор вопрос-ответ.
Тогда язык, соответствующий задаче -- набор вопросов, для которых ответ ``да''. Значит, например,
для задачи коммивояжёра языка не существует. Пример языка, не принадлежащего $NP$: множество
программ, которые закончивают работу. Задача проверки при\-над\-леж\-но\-сти программы к этому языку
алгоритмически неразрешима, значит, не существует под\-ска\-зок: ведь тогда существовал бы и алгоритм
проверки, основанный на переборе подсказок.\par
Итак, $NP$ -- задача, которую можно решить перебором всех $y$ (ведь $y$ должен быть
полиномиального размера от $x$, и для каждого $y$ мы можем запустить полиномиальный $P$. Только
если хоть раз $P(x,y)=1$, наш $x\in L$).\par
В этой лекции мы будем доказывать только теоремы вида ``$x$ при\-над\-ле\-жит языку $L$''. Если
$L\in NP$, то доказательство очень простое -- предъ\-явить $y$, и запустить алгоритм $P$.
Значит, обычные теоремы с константной или даже полиномиальной (от условия) длинной
доказательства образуют язык класса $NP$, где доказательство и есть подсказка. И наоборот:
самый общий вид теоремы: ``строка $\{0,\ 1\}^n$ при\-над\-ле\-жит к языку $L$''.\par
Итак, в интерактивном доказательстве участвуют \prover rover и \verifier erifier. \prover\
хочет убедить \verifier, что рассматривамый ими $x$ лежит в заданном языке $L$.
Они обмнениваются сообщениями, и через конечное число раундов \verifier должен либо признать
доказательство верным, либо высказать от\-ри\-ца\-ние этого. Требования к доказательству:
\begin{itemize}
\item Полнота: $\forall x\in L, \exists \prover : [\prover(x),\verifier(x)]=1.$
\item Корректность: $\forall x\notin L, \forall \prover ' : Pr([\prover '(x),\verifier(x)]=1)=\nu(|x|).$
\end{itemize}
($\nu(|x|)$ -- фукция, убывающя быстрее обратной к полиному). То есть: сна\-ча\-ла \prover\ шлет \verifier\
первое приближение доказательства. Тот задаёт какой-то во\-прос. \prover\ уточняет доказательство,
и так далее. Полнота означает, что про любой $x$ из $L$ можно так доказать теорему, а корректность
-- что вероятность того, что \verifier\ поверит в доказательство для $x\notin L$ очень мала.

\section{Примеры интерактивных доказательств}
Мы считаем, что \verifier erifier пользуется полиномиальным вероятностным ал\-го\-рит\-мом,
а \prover rover вычислительно не ограничен. Это в частности означает, что \verifier\
возможно проверяет доказательство не целиком, а выборочно. То есть условно он предлагает
\prover\ некий тест из нескольких раундов, который тот пытается пройти. Заметим, что
очень просто доказать за один раунд при\-над\-леж\-ность $x$ к языку $NP$ (подумайте сами, ответ
уже звучал в пун\-кте \textbf{\textsf{1.5}}.) Тогда $IP$ -- класс всех языков, принадлежность к
которым можно интерактивно доказать. Учёные задумались над видом этого класса. За\-ме\-тим, что
$IP \subset PSPACE,$ ведь \verifier\ может просто перебрать все подсказки, каждый раз при
переходе к новой стирая память, каждый раз вызывая $P$, ведь по\-ли\-но\-ми\-аль\-ный алгоритм не
может занять более чем по\-ли\-но\-ми\-аль\-ный объём памяти за время своей работы. Верно и более сильное:
Теорема [Шамир, 1990]: $IP$ = $PSPACE$.\par
Первый пример доказательства (изоморфизм графов): \prover\ собирается доказать
$G_0\cong G_1$. Он знает изоморфизм $\phi$.
\begin{enumerate}
 \item \prover\ выбирает случайную перестановку $\pi$ и посылает $\pi\ (G_1) = H$
 \item \verifier\ посылает случайное $b$ ($b = \{0,\ 1\}$), т. е. просит либо изоморфизм
 $H\cong G_0,$ либо $H\cong G_1.$
 \item В зависимости от $b$, \prover\ посылает $\pi$ или $\pi \circ \phi$
 \item Шаги 1-3 повторяются 1000 раз
\end{enumerate}
Полнота следует из транзитивности изоморфизма. Каковы шансы пройти тест при $G_0\ncong G_1$?
Вне зависимости от количества вершин шансы равны $1/2^{1000}$ (вероятность). Значит, имеет место
и корректность.\par
Второй пример доказательства (не-изоморфизм графов): \prover\ собирается доказать $G_0\ncong G_1$.
\begin{enumerate}
 \item \verifier\ выбирает случайное $b$ и случайную перестановку $\pi$ и посылает $\pi\ (G_b) = H$
 \item \prover\ пытается угадать $b$ по $H$
 \item Шаги 1-2 повторяются 1000 раз
\end{enumerate}
Полнота верна, так как посылаемый граф $H$ изоморфен ровно одному из $\{G_0,\ G_1\}$
Если же графы изоморфны, то $H$ Может быть получено как из $G_0,$ так и из $G_1.$ Значит,
вероятность угадать для \prover\ в таком случае равна опять же $1/2^{1000},$ то есть
доказательство корректно.\par
Третий пример доказательства (3-раскрашиваемость, т. е. возможность раскрасить данный граф
в 3 цвета так, чтобы инциндентные вершины были разных цветов, это {\it NP-полная} задача).
(То есть если есть $\forall G_0, G_1$ $\exists H$: $G_0\cong G_1 \Leftrightarrow H$ --
3-раскрашиваем).\par
Покажем доказательство 3-раскрашиваемости:
\begin{enumerate}
 \item \prover\ случайным образом переставляет три цвета между
 собой
 \item \prover\ коммитит (т.е. использует привязку к биту) цвета
 всех вершин
 \item \verifier\ выбирает случайную пару вершин, соединённых ребром
 \item \prover\ открывает цвета этих вершин
 \item Шаги 1-4 повторяются $1000n^2$ раз
\end{enumerate}
Если существовала раскраска -- то всё верно, значит корректность есть. Если же нет,
то вероятность угадать за $n^2$ раз равна $(1-\frac {1}{n^2})^{n^2} = \frac {1}{e}$, а
вероятность угадать за $1000n^2$ раундов равна $(1-\frac {1}{1000n^2})^{1000n^2} = \frac {1}{e^{1000}}.$
Давайте заметим, что \verifier\ ничего не узнал про раскраску графа (здесь важ\-но, что он может
спрашивать только про соединённые ребром вершины, и на том, что он не может расшифровать
зашифрованные цвета). Так мы подходим к понятию нулевого разглашения, как к ещё одному
(не\-обяза\-тель\-но\-му) свойству интерактивного доказательства, однако оно нуждается в более формальном
определении.

\section {Нулевое разглашение (Определение, до\-ка\-за\-тель\-ство)}
\subsection {Подготовка}
Напомним, у \prover\ и \verifier\ есть теорема о принадлежности строчки $x$ к языку $L$. Мы хотим
определить, что значит, что доказательство не раскрывает никакой информации о\dots о чём же?
Об обычном доказательстве? Или о каких-то ``тайных знаниях'' \prover rover'а? А что это такое?
Может быть, нулевое разглашение -- это такое свойство, которое после интерактивного
до\-ка\-за\-тель\-ства не гарантирует \verifier erifier'у возножность самостоятельно
``не-интер\-ак\-тив\-но'' доказать теорему? Но ведь он {\it всегда} может это сделать, так как мы
уже доказали, что $IP \subset PSPACE!$ И тогда \verifier erifier может разобраться, верна ли
теорема, перебирая подсказки. Можно сказать так -- мы должны ``мало'' узнать про $х$. Но мы
хотим в общем случае определить нулевое разглашение, не определяя каждый раз заново секрет
(для изо\-морф\-ных графов это был сам изо\-мор\-физм, для 3-раскрашиваемости -- сама рас\-крас\-ка.)
Но мы уже можем определить ``не-секрет'': им является то, что можно вывести из условия
полиномиальным алгоритмом. Итак, на\-бро\-сок определения: интерактивное доказательство обладает
{\it нулевым раз\-гла\-ше\-ни\-ем}, если все что \verifier\ узнал об $x$, он мог вычислить самостоятельно.\par

\subsection {Формальное определение}
Первая попытка: пара алгоритмов (\prover, \verifier), образующих интерактивное
доказательство, обладает нулевым разглашением, если:
$$\exists \textsf{S}_{PPT} \forall x\in L: VIEW_{\prover,\verifier}[x]=S[x],$$
где $VIEW_{\prover,\verifier}$ -- последовательность сообщений, полученных \verifier.\par
То есть \verifier\ может самостоятельно ``симулировать'' диалог с \prover.
$\exists \textsf{S}_{PPT}$ оз\-на\-ча\-ет, что существует полиномиальный вероятностный
алгоритм $S$, ко\-то\-рый может не зная ничего, кроме условия теоремы симулировать
\prover rover, то есть сгенерировать последовательность сообщений между ним и \verifier\ (на самом деле
в этом нет ничего удивительного, ибо он может её {\it угадать}). Но это определение обладает
каким-то недостатком. Каким? Верно ли, что мы гарантировали ``точное'' неразглашение?
Как мы здесь комментируем неразглашение? ``Мы могли бы запустить симулятор и узнать из него.''
Значит, подвох в том, что мы можем узнать из \prover rover'а то, чего нельзя узнать из симулятора.
Это можно сделать, если \verifier\ жульничает при диа\-логе. Тогда мы будем иметь дело не с
$VIEW_{\prover,\verifier}[x]$, а с $VIEW_{\prover,{\textsc{\textbf{V'}}}}[x]!$ И нам важно
гарантировать, что и в этом случае \verifier\ не получит никакой ин\-фор\-ма\-ции. Например, если
\verifier\ в приведённых выше интерактивных до\-ка\-за\-тель\-ствах ведёт себя не случайным образом,
а с каким-то подвохом.\par
Вторая попытка (окончательное определение):
$$\forall \textsf{\textbf{V'}}\ \exists \textsf{S}_{PPT}\ \forall x\in L: VIEW_{\prover,\textsf{\textbf{V'}}}[x]=\textsf{S}{[x]\ (*)}$$
Так же вводится еще более сильное свойство (симулятор с оракульным доступом):
$$\exists \textsf{S}_{PPT}\ \forall \textsf{\textbf{V'}}\ \forall x\in L: VIEW_{\prover,\textsf{\textbf{V'}}}[x]=\textsf{S}^{V'}[x]$$
Здесь мы усилили свойство, требуя один единственный алгоритм, не ин\-те\-ре\-сую\-щий\-ся внутренностью
\verifier erifier'а.

\subsection {Применения нулевого разглашения}
\begin{itemize}
\item Многосторонние вычисления --- взаимный контроль участников.
\item Протоколы авторизации -- подслушивание бесполезно! Это настоящая революция: вместо
того, чтобы присылать пароль, пользователь про\-хо\-дит набор тестов, не подсказавающих
злоумышленнику этого па\-ро\-ля!!!
\item Электронные выборы -- возможность избирателя доказать, что он не зашифровал голоса
за несколько человек, не раскрыв свой голос.
\item Электронные деньги: мы подписываем у банка банкноту в 100\$, не раскрывая сам текст,
написанный на ней.
\item Или византийские генералы: если генерал может послать за\-шифр\-ован\-ные приказы, и,
например, не раскрывая их, доказать, что они одинаковы.
\end{itemize}
\subsection {Доказательство нулевого разглашения для изо\-мор\-физ\-ма графов}
Напомним наш алгоритм доказательства изоморфности:
\begin{enumerate}
 \item \prover\ выбирает случайную перестановку $\pi$ и посылает $\pi\ (G_1) = H$
 \item \verifier\ посылает случайное $b$ ($b = \{0,\ 1\}$), т. е. просит либо изоморфизм
 $H\cong G_0,$ либо $H\cong G_1.$
 \item В зависимости от $b$, \prover\ посылает $\pi$ или $\pi \circ \phi$
 \item Шаги 1-3 повторяются много раз
\end{enumerate}
Давайте сначала обсудим его неразглашаемость неформально. \verifier erifier видит
некий граф $H,$ изоморфный одному из двух исходных и изоморфизм к нему. Помогает ли это
нам установить исходный изоморфизм? Ничуть. Но на самом деле всё не так просто, ведь \verifier\
может ``чуть-чуть при\-гля\-деть\-ся'' к $H$ и понять, какому из $G_0, G_1$ он вероятнее изоморфен
(если, к примеру, \prover\ не очень силино его изменил). Давайте убедимся, что это всё-таки
не облегчает жизнь \verifier erifier'у. Мы должны доказать, что для каждого выбора теста
существует программа $S$, которая для любого входа $x$ генерирует настоящий диалог \verifier\
с \prover. Вопрос: что за объекты стоят слева и справа в равенстве $(*)$? Ответ: потоки сообщений.
И равенство это значит, что программа $S$ генерирует те и только те потоки сообщений, которые могли
получиться в результате общения \prover\ и \textsc{\textbf{V'}}, и каждый кон\-крет\-ный поток
получается с точно такой же вероятностью, т. е. рас\-пре\-де\-ле\-ния вероятности и справа и слева
одинаковы. Итак, алгоритм симулятора:
\begin{enumerate}
 \item Выбираем случайное $b$, случайную перестановку $\pi$
 \item Скармливаем граф $\pi\ (G_b)$ алгоритму \textsf{\textbf{V'}}
 \item Если \verifierst\ просит показать изоморфизм для $G_b$ -- показываем
 $\pi$, если для $G_{\bar b}$ --- сбрасываем память \verifierst\ и пробуем
 еще раз
 \item Цикл по шагам 1-3 повторяем до 1000 успешных итераций
\end{enumerate}
Вопрос: какова вероятность того, что \verifierst\ попросит на шаге $n$ тот изо\-мор\-физм,
который мы знаем? Ответ: на каждом шаге $1/2.$ Следовательно, ма\-те\-ма\-ти\-чес\-кое ожидание
работы симулятора --- полиномиально. Точнее, в данном случае оно равно $2000$ раундов. Значит,
вероятность {\it не пройти} весь симулятор за $10^6$ шагов -- очень мала, и равна $1/2^{1000}.$
Вопрос: а вдруг нельзя сбросить память у \verifierst? Но ведь \verifierst\ с $S$ заодно,
значит, всё-таки можно.\par
Итак, на данный момент мы симулятором построили по\-сле\-до\-ва\-тель\-ность сообщений,
которая {\it могла быть} в действительности. Но мы не проверили, что так можно
сгенерировать {\it каждый} из возможных диалогов, причём равновероятно. Давайте убедимся в этом:
 \begin{itemize}
  \item Фазы независимы между собой
  \item Мы включаем/не включаем фазы {\it независимо} от их
  содержания
\end{itemize}
Аналогия:
\begin{itemize}
 \item Студент стоит спиной к доске. Профессор выписал случайную по\-сле\-до\-ва\-тель\-ность. 
Студент говорит, какие символы вычеркнуть. То, что осталось -- случайная последовательность
(если профессор честный)!
\end{itemize}
С симулятором всё абсолютно так же: мы выбираем {\it случайно} первую фазу, так же случайно, как
и \prover rover. Затем \verifier erifier, не зная, из какого мы построили граф $H,$ (из $G_0$ или $G_1$),
говорит, какой изоморфизм ему хотелось бы получить. Значит, те попытки, которые мы не выкинем,
ос\-та\-нут\-ся в нашей окончательной последовательности сообщений с такой же вероятностью, как и в
настоящем диалоге интерактивного доказательства. Значит, мы доказали, что для нашего $S$ и справа,
и слева в равенстве (*) получится одно и то же. Что и требовалось!

\subsection {Ещё более сложная проблема}
До сих пор открытой является проблема для случая, когда \prover rover {\it од\-но\-вре\-мен\-но}
присылает \verifier erifier'у графы, а тот сразу для всех них генерит тест (какой он требует
изоморфизм - к $G_0$ или к $G_1$), и \prover\ сразу на все вопросы теста отвечает. Для такого
протокола пока ещё никто не умеет доказать свойство нулевого разглашения!!! Наше доказательство
не проходит - ведь теперь шанс закончить работу равен $1/2^{1000}.$

\subsection {Задачи на дом}
\begin{enumerate}
 \item Доказать, что $IP \subseteq PSPACE.$
 \item Нулевое разглашение для квадратичных вычетов по составному мо\-ду\-лю:
рассмотрим только те остатки $x$ в классе вычетов по модулю $N = pq,$ где $p$ и $q$ -- простые, 
которые дают либо квадратичный вычет по модулю $N$ (т. е. $\exists y \in \mathbb Z_n:\ x\equiv y^2 \mod N$),
либо не являются квадратичным вычетом ни по модулю $p,$ ни по модулю $q.$ Наш язык $Li$ состоит только
из тех остатков, которые всё же дают квадратичный вычет по модулю $N.$ Задание состоит в том,
чтобы придумать такое интерактивное доказательство с нулевым разглашением, которое до\-ка\-зы\-ва\-ет
при\-над\-леж\-ность рассматривавемого остатка к языку $Li.$ Пример: $N = 15,$ тогда $Li = \{1,\ 4\}$
(а рассматриваем мы в этом примере все $x: x \in \{1, 4, 7, 11, 13\}$).
\end{enumerate}

\subsection {Использованные материалы}
\begin{enumerate}
 \item Презентация, предоставленная докладчиком -- Ю. Лифшицом
 \item Бумажный конспект лекции
 \item Звукозапись слов докладчика
 \item Текстовый редактор UltraEdit-32 v.10.10c
 \item T{\it e}X-поставка EXTEX
 \item Программа для просмотра PostScript -- GsView v.4.3
 \item Adobe Acrobat Distiller Professional Version 6.0
\end{enumerate}

\end{document}