\documentclass{article}
\usepackage[cp1251]{inputenc}
\usepackage[russian]{babel}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{supertabular}

\title{Нулевое разглашение для языков из NP}
\author{Ю. Лифшиц\thanks{Законспектировал В. Столбов .}.}

\begin{document}
\maketitle

\section*{План лекции}
\begin{enumerate}
\item Нулевое разглашение для NISO

\item Нулевое раазглашение для
языков из NP

\item Нулевое разглашение для задачи 3-раскрашиваемости

\item Формулировка теоремы
\end{enumerate}
\par

\section{Нулевое разглашение для NISO}
   На предыдущей лекции был приведен протокол интерактивного
   доказательства неизоморфности графов $ G_{1} $ и $ G_{2} $
\begin{enumerate}
    \item V выбирает случайное $ b\in [1,2] $ и случайную перестановку
    $ \pi $
    \item V посылает  P $ \pi (G_{b}) $
    \item P угадывает b и посылает  V
    \item  шаги 1-3 повторяются достаточно большое число раз
\end{enumerate}
\par
Свойства полноты и корректности для данного протокола очевидны. Но
он не обладает свойством нулевого разглашения, так как для любого
графа  $ G_{0} $ V может определить, какому из графов  $ G_{1}$ ,
$ G_{2}$ он не изоморфен. Тем не менее существует протокол
доказательства NISO с нулевым разглашением.
\par


\section{Нулевое разглашение для языков из NP}
\subsection{Напоминания}
\begin{enumerate}
   \item Язык L принадлежит классу языков  NP, если  $ \exists $
   полиномиальный P, такой что  $(x\in L)\Leftrightarrow \exists y
   (P(x,y)=1)$.
   \item Язык L является NP-полным, если $\forall L_{1} \in NP \exists
   poly f  x \in L_{1} \Leftrightarrow f(x) \in L $
   \item  Язык 3-раскрашиваемых графов является NP-полным.
\end{enumerate}
\par
 Уточнение 1  - f из свойства 2 является инъекцией.

\subsection{Доказательства с нулевым разглашением для языков из NP}
  Допустим, что мы знаем протокол, доказывающий с нулевым
  разглашением задачу 3-раскрашиваемости.
  Пусть L - некий язык из NP (например, язык составных чисел),
  а  f - отображение, сопоставляющее каждому натуральному числу некий граф,
  являющийся 3-раскрашиваемым тогда и только тогда, когда это число
  составное.
\par
  Тогда рассмотрим протокол:
\par
\begin{enumerate}
 \item V и P вычисляют $G(x)$
\item P ( в нашей модели он вычислительно неограничен ) находит
 3- раскраску G
\item Осуществляется протокол интерактивного доказательства
3-раскрашиваемости графа G
\end{enumerate}
\par
 Полнота и корректность данного протокола очевидны.
Доказательство  свойства нулевого разглашения тоже очевидно -
 $VIEW[V,P]$ и $VIEW[V_{1}, P_{1}]$ совпадают ( $V_{1}$ и $P_{1}$ -
 участники протокола доказательства 3-раскрашиваемости графа. )
  Таким образом, из нулевого разглашения для протокола
  3-раскрашиваемости по определению следует нулевое разглашение для
  предыдущего протокола.
\section {Нулевое разглашение для задачи 3- раскрашиваемости}
 \subsection {Уточнение определения}
  \par  Знак изоморфизма в определении
  \par $\forall V_{1} \exists S_{PPT} \forall x \in L VIEW[V_{1}, P]\cong S(x) $
  \par означает, что распределения ответов у вероятностных
  алгоритмов  совпадают.
  \par
 \subsection {Нулевое разглашение в слабом смысле}
  $S_{PPT}$ и $R_{PPT}$ называются вычислительно неразличимыми,
  если не существует полиномиального P, способного по результату
  работы одного из этих алгоритмов определить, какой именно
  алгоритм был запущен.
 \par  Протокол интерактивного доказательства называется
 протоколом с ненулевым разглашением в слабом смысле, если условие
 совпадения распределений заменено на условие вычислительной
 неразличимости.
 \par
 \subsection {Протокол доказательства 3-раскрашиваемости}
  \begin{enumerate}
  \item P случайным образом переставляет цвета.
  \item P шифрует цвета, используя привязку к биту и посылает
  зашифрованную раскраску  V
  \item V выбирает 2 вершины, соединенные ребром, и посылает P их номера.
  \item P расшифровывает цвета  указанных вершин.
  \item V проверяет, что цвета вершин не совпадают.
  \item Шаги 1-5 повторяются много раз (рекомендуется порядка числа
  ребер).
  \end{enumerate}
\par
  Полнота и корректность достаточно очевидны. Осталось доказать,
что данный протокол обладает свойством нулевого разглашения в
слабом смысле.

\subsection {Построение $S_{PPT}$}
  \begin{enumerate}
    \item S выбирает 2 соединенные ребром вершины $V_{1}$ ,
    $V_{2}$, красит их в различные цвета, а все
    остальные - в красный.
    \item S шифрует цвета, используя привязку к биту и посылает
  зашифрованную раскраску  V
   \item V выбирает 2 вершины, соединенные ребром, и посылает S их номера.
   \item Если V выбрал $V_{1}$ и $V_{2}$, S расшифровывает цвета,
   иначе стирает V память.
  \end{enumerate}
\par
 \subsection {Доказательство свойства ненулевого разглашения в слабом смысле.}
   Доказательство будет проводиться методом black-box reduction.
   Точнее, докажем, что если кто-то сумеет за полиномиальное время
   отличить симулятор от настоящего диалога, то шифрование
   является нестойким.
\par
  Предположим противное.
  Пусть $\exists V$, который умеет отличать сообщения от S и
  сообщения от P.
\par
  Тогда рассмотрим набор алгоритмов $I_{i}$,  где i изменяется от
  0 до n- 2. $I_{i}$ выбирает i+2 вершины, раскрашивает их
  правильной 3- раскраской, а все остальные красит в красный,
  шифрует цвета, используя привязку к биту и посылает все это V.
  Заметим что сообщения от $I_{0}$  совпадают с сообщениями от S,
  а сообщения от $I_{n-2}$ совпадают с сообщениями от P.
  Значит, найдется k, такой что V различит сообщения от
  $I_{k}$ и от $I_{k+1}$. но эти сообщения отличаются шифром
  цвета одной вершины. Таким образом, с вероятностью  $n^{-1}$
  шифрограмму можно сломать. Таким образом, шифрование нестойкое.

\section {Формулировка теоремы}
\begin{enumerate}
\item $\forall L \in NP \exists$ протокол интерактивного
доказательства теорем вида  $x \in L$ с нулевым разглашением.
\item Стойкость протокола основана на стойкости шифрования.
\end{enumerate}

\section {Использованные материалы}
\begin{enumerate}
\item Бумажный конспект лекции.
\item WinEdit 5.3
\end{enumerate}


\end{document}