\documentclass{article} \usepackage[russian]{babel} \usepackage{amssymb} \usepackage{amsmath} \usepackage{supertabular} \title{Византийское соглашение и покер по телефону} \author{Ю. Лифшиц\thanks{Законспектировал А. Диевский.}.} \begin{document} \maketitle \section*{План лекции} \begin{enumerate} \item Неформальная постановка задач \item Византийское соглашение \item Покер по телефону \item Пример работы византийского протокола \end{enumerate} \par \section{Неформальная постановка задач} \subsection{Автопилоты} Представим себе, что по небу летит самолет. На автопилоте. А теперь пред\-ста\-вим, что этот автопилот сломался. Ничего хорошего не произойдет, не так ли? Как бороться с такой ситуацией? Ясное дело, поставить еще один независимый автопилот. Но которого из них слушаться, когда они дают разные указания? Из двух автопилотов ни один не способен образовать большинство. Значит, надо поставить три автопилота! Даже если один из них сломается, остальных все равно будет больше, и они смогут принять правильное решение голосованием! Но кто будет проводить это голосование? Некий контрольный центр? Но если сломается он, то все усилия пойдут насмарку. Значит, автопилоты должны договориться между собой и сами прийти к правильному решению. \par К сожалению, это невозможно. Вернее, это невозможно для трех авто\-пи\-ло\-тов. А вот для четырех, из которых испортилось не более одного, необходимый протокол существует, и он будет предъявлен. \subsection{Карты по телефону} Предположим, что неугомонные Алиса и Боб решили сыграть в карты. Вот только они живут в разных городах, и из средств связи у них есть только телефон. Казалось бы, сыграть честную партию по телефону невозможно. И это действительно невозможно. Но, с другой стороны, протокол для такой игры известен довольно давно, и он будет предъявлен. Почему в этих двух утверждениях нет противоречия? Попробуйте догадаться сами, а если не догадаетесь - в конце третьего раздела мы вам расскажем. \section{Византийское соглашение} \subsection{Византийские генералы} В изначальной постановке задачи никаких автопилотов не было, а было $n$ византийских отрядов, осаждающих вражеский город. Каждым отрядом командовал независимый генерал. Генералы могли общаться друг с другом по закрытому каналу, например, с помощью голубиной почты. Все вместе они общаться не могли, потому что отряды стояли далеко друг от друга, а радио и Интернет еще не изобрели. Все знали, что враг хитер и коварен, и вполне мог подкупить кого-нибудь из генералов; оставалось надеяться, что генералов-предателей не очень много. Тем временем осада затягивалась, пора было переходить к решительным действиям. Да вот беда - генералы не могли собраться вместе и выработать единый план. Если бы не угроза предательства, все было бы просто - каждый генерал изложил бы остальным свой план с помощью голубей, а затем каждый выбрал бы наиболее попу\-ляр\-ный план и действовал бы согласно ему. Но так поступить нельзя - а ну как предатель скажет одному генералу, что пора наступать, а другому - что лучше отойти? Половина генералов рванется в бой, половина отступит, и получится черт знает что. \par Таким образом, нужен был протокол, отвечающий двум требованиям: \begin{enumerate} \item Все честные генералы должны в итоге принять одно и то же решение. \item Если предателей не очень много, то это решение должно оказаться правильным. \end{enumerate} Сам протокол, по-видимому, должен состоять из двух фаз: \begin{itemize} \item[Фаза 1.] Генералы обмениваются информацией. \item[Фаза 2.] Генералы принимают решение на основе полученной информации. \end{itemize} Если мы в ходе первой фазы сделаем так, чтобы все генералы получили одинаковую сводку информации, то вторая фаза будет очень простой - выбрать наиболее популярный план из $n$ предложенных. Таким образом, от первой фазы мы требуем два условия: \begin{itemize} \item[1А.] Информация честных генералов должна дойти до остальных неиска\-жен\-ной. \item[1Б.] От любого генерала все должны получить одинаковую информацию, даже если он попытается сообщить разную. \end{itemize} Далее мы для простоты будем считать, что каждый генерал делает бинарный выбор, например, выбирает между атакой и отступлением. \subsection{Командир и его заместители} Ясно, что изложенная выше задача разбивается на $n$ одинаковых подзадач - каждый генерал должен передать свой выбор остальным. Эти подзадачи эквивалентны задаче о командире, который должен передать свой приказ $n-1$ заместителям, причем предателями могут быть как заместители, так и командир. От такого протокола мы опять потребуем два похожих свойства: \begin{enumerate} \item \textbf{Согласованность} Все честные заместители должны поступить оди\-на\-ко\-во. \item \textbf{Исполнительность} Если вдобавок командир честен, то есть отдал всем одинаковый приказ, а среди заместителей не слишком много предателей, то все честные заместители должны поступить так, как приказал командир. \end{enumerate} В этой схеме каждый может общаться с каждым. Докажем от против\-но\-го, что для $n=3$ и не более чем одного предателя требуемый протокол невозможен. \par Первая ситуация. Пусть командир и первый заместитель - честны, а второй заместитель - предатель. Командир отдает приказ атаковать, однако второй заместитель, желая запутать первого, говорит ему, что командир приказал отступать. Наш предполагаемый протокол должен обладать испол\-ни\-тельностью, поэтому честный первый заместитель должен выполнить приказ командира, то есть пойти в атаку, игнорируя своего коллегу. Таким образом, выходит, что заместитель должен в любом случае слушаться коман\-ди\-ра. \par Вторая ситуация. Пусть теперь предатель - командир. Он отдает первому заместителю приказ атаковать, а второму - отступать. Честные заместители честно сообщают друг другу эти приказы, но, согласно предыдущему вы\-во\-ду, игнорируют разночтения, так что первый заместитель идет в атаку, а второй отступает. Стоп! Мы потеряли согласованность. \par Это и доказывает невозможность такого протокола. \subsection{Протокол для $n \geq 3m+1$} В предыдущем пункте беда была в том, что предателей было \textit{не менее од\-ной трети}. Сейчас мы построим протокол, обладающий нужными свойствами, если предателей менее одной трети. Строить будем по индукции по числу $m$, где, как потом окажется, $m$ - это максимальное число предателей, для которого протокол все еще работает. Напомним, что мы сейчас рассматри\-ва\-ем не задачу о генералах, а более простую задачу о командире и замести\-те\-лях, причем с бинарным выбором приказа. \par \vspace{.5cm} \textbf{Протокол $BG(0)$.} \par \begin{enumerate} \item Командир рассылает заместителям приказ. \item Заместители поступают в соответствии с полученным от коман\-ди\-ра приказом. \end{enumerate} Заметим вскользь, что для случая, когда предателей нет, протокол пре\-крас\-но работает. \par \vspace{.5cm} \textbf{Протокол $BG(m)$.} \par \begin{enumerate} \item Командир рассылает заместителям приказ. \item Каждый заместитель рассылает этот приказ своим коллегам, исполь\-зуя протокол $BG(m-1)$. На время рассылки рассылающий замести\-тель играет роль <<командира>> среди своих коллег. \item Каждый заместитель из $n-1$ приказа (одного <<своего>> и $n-2$ полу\-чен\-ных от коллег) выбирает наиболее часто встречающийся и поступает в соответствии с ним. \end{enumerate} Тут необходимо сделать одну оговорку. К сожалению, может случиться так, что наиболее частого плана не будет (рассмотрите самостоятельно случай, когда командир-предатель приказывает одной паре честных замес\-ти\-те\-лей атаковать, а другой - отступать, используя протокол $BG(1)$). Поэто\-му мы будем считать, что заранее оговорен <<план по умолчанию>>, которому все следуют в случае <<ничьей>>. \par \textbf{Лемма.} Для любых натуральных чисел $k$, $m$ протокол $BG(m)$ обладает исполнительностью, если $n \geq 2k+m+1$, а предателей не больше $k$. \par \textbf{Доказательство.} Индукция по $m$. \par \textbf{База: $m=0$.} В самом деле, все честные заместители поступят в соответ\-ствии с полученным правильным приказом. \par \textbf{Переход: $m-1 \mapsto m$.} Всякий честный заместитель, получив приказ, рассылает его коллегам по $BG(m-1)$. При этом участников этой рассылки $n-1$ (все, кроме командира), то есть не менее $2k+m$, а предателей среди них по прежнему не более $k$. По предположению индукции, в этом случае $BG(m-1)$ обладает исполнительностью, а стало быть, честные заместители правильно передадут коллегам правильный приказ командира. В этом слу\-чае у каждого заместителя окажется не менее $k+m+1$ правильных копий приказа (не более чем $k$ предательских копий окажутся неправильными), а это в любом случае больше половины. Таким образом, каждый честный заместитель выполнит правильный приказ. \par Доказательство завершено. \par Теперь докажем основную теорему. \par \textbf{Теорема о корректности $BG(m)$.} Для любого натурального $m$ про\-то\-кол $BG(m)$ обладает согласованностью и исполнительностью, если $n \geq 3m+1$, а предателей не более $m$. \par \textbf{Доказательство.} Исполнительность следует из леммы при $k=m$. Согласованность будем доказывать по индукции по $m$. \par \textbf{База: $m=0$.} Раз предателей нет вовсе, то все получат одинаковый приказ и выполнят его. \par \textbf{Переход: $m-1 \mapsto m$.} Если командир честен, то согласованность следует из исполнительности (все правильные приказы одинаковы), а исполни\-тель\-ность уже доказана. Пусть теперь командир предатель. Заместителей не менее $3m$, а предателей среди них - не более $m-1$, поэтому по предполо\-же\-нию индукции протокол $BG(m-1)$ среди заместителей обладает согласован\-но\-стью. Поэтому копия приказа, пересланная каждым из заместителей кол\-ле\-гам, будет принята всеми одинаково. Это означает, что все честные заме\-сти\-те\-ли получат одно и то же представление о приказах, полученных дру\-ги\-ми заместителями. Это, в свою очередь, означает, что у честных заме\-сти\-те\-лей будет совпадать <<сводка приказов>>. Но в этом случае они все примут одинаковое решение. \par Доказательство завершено. \par \vspace{.5cm} Как мы видим, построенный нами протокол работает и отвечает всем требованиям при соблюдении приведенных выше условий (менее трети пре\-да\-те\-лей). Можно доказать, что для случая, когда предателей не менее трети, протокол такого вида невозможен. Это доказательство сводится к уже рас\-смот\-рен\-ному случаю <<один из трех>>. \par Как легко видеть, протокол довольно громоздок. Можно доказать, что при фиксированном $m$ число сообщений в протоколе $BG(m)$ асимптоти\-че\-ски равно $n^{m+1}$ (в случае командира и заместителей) или $n^{m+2}$ (в случае гене\-ра\-лов) при большом $n$. \par В конце конспекта приведено два примера для $n=4$, $m=1$. \par \section{Покер по телефону} \subsection{Требования к протоколу} Итак, второй нашей задачей было изучить возможность сыграть партию в карты по телефону. Основной трудностью здесь, конечно, является раздача карт. Мы предъявим к ней вполне очевидные требования: \begin{itemize} \item Раздача должна быть случайной. \item Карты игроков не должны пересекаться. \item Игрок не должен иметь возможности узнать что-либо о картах других игроков, кроме того, что у них другие карты, чем у него. \item Должна быть возможность по ходу партии добирать карты. \item Должна быть возможность в конце партии проверить честность иг\-ро\-ков. \end{itemize} \subsection{Невозможность} Предположим, что мы придумали такой протокол. Ясно, что раздача карт должна представлять собой обмен сообщениями $M_1, M_2, \ldots,M_n$ между Али\-сой и Бобом, при этом у них обоих может быть своя секретная информация (например, закрытый ключ шифрования) $R_A$ и $R_B$. Тогда результат раздачи должен быть представлен как функция $f_A(R_A,M_1,\ldots,M_n)$ для Алисы и $f_B(R_B,M_1, \ldots,M_n)$ для Боба. Для возможности проверки честности функ\-ции $f_A, f_B$ должны быть заранее оговорены обоими игроками. \par Предположим, что в игре всего три карты $\{ X,Y,Z \}$, и в результате раздачи Алисе достался $X$, а Бобу $Y$. Заметим, что существует такое $R'_A$, что $f_A(R'_A,M_1,\ldots,M_n)=Z$ - иначе Боб по известным ему сообщениям $M_k$ и по тому, что у него карта $Y$, мог бы догадаться, что у Алисы $Z$. Однако из тех же соображений существует такое $R'_B$, что $f_B(R'_B,M_1,\ldots,M_n)=Z$. Таким образом, если Алиса и Боб одновременно задумают $R'_A$ и $R'_B$ соответственно, то оба получат карту $Z$, что явно противоречит условию о непересекаемости карт. \par Это доказывает принципиальную невозможность требуемого протокола. \par \subsection{Предъявление} Однако сейчас мы предъявим протокол, с помощью которого можно играть в карты по телефону. Для этого нам потребуется понятие коммутативного шифрования. \par Вот задача на сообразительность. Пусть на одном берегу реки стоит Алиса, которая проиграла Бобу в карты по телефону большой алмаз. Боб, естественно, стоит на другом берегу. Единственное средство сообщения ме\-жду ними - паром со встроенным в него сейфом без замка. Причем па\-ром\-щик уже жадно заглядывается на алмаз в руках Алисы. Однако по счастливой случайности у Алисы и Боба есть по навесному замку с ключом (у каждого свой). Как переправить алмаз, не дав паромщику шанса его присвоить? \par Ответ прост: Алиса кладет алмаз в сейф, запирает его на замок и от\-прав\-ля\-ет Бобу. Боб не пытается взломать сейф, а вместо этого навешивает рядом с алисиным замком свой и отправляет паром к Алисе. Алиса, увидев, что сейф закрыт на замок Боба, снимает свой замок и отправляет сейф обратно. Боб, наконец, снимает свой замок и забирает желанный алмаз. \par Вполне возможно, что именно эта задачка послужила отправной точкой при создании методов коммутативного шифрования. Здесь важно, что замки на сейф можно навешивать и снимать \textit{независимо друг от друга}. Точно так же, если имеются две криптосистемы $E_1$ и $E_2$ (функции, сопоставляющие исходному сообщению шифрованное), обладающие свойством $E_1 \circ E_2 = E_2 \circ E_1$, то такие системы называются \textit{коммутирующими}. \par Примером таких систем могут служить две системы RSA по одинаковому модулю, так как $(t^{e_1})^{e_2} = (t^{e_2})^{e_1}$. \par Итак, вот наш протокол для игры в покер. \par \begin{enumerate} \item Алиса и Боб тайно друг от друга выбирают две коммутирующие крип\-то\-сис\-темы. \item Алиса зашифровывает своим ключом все 52 карты, перемешивает их и отправляет шифрограммы Бобу. \item Боб случайным образом выбирает из них 5 шифрограмм для Алисы и отправляет их ей. \item Алиса с помощью своей криптосистемы расшифровывает свои карты. \item Боб случайным образом выбирает из оставшихся шифрограмм 5 для себя, зашифровывает их своим ключом и отправляет Алисе. \item Алиса расшифровывает их своим ключом и отправляет их Бобу. \item Боб окончательно расшифровывает свои карты своим ключом. \item Если игрокам потребуется добрать карты из колоды, применяется аналогичная последовательность действий. \end{enumerate} Этот протокол, казалось бы, хорош. Боб не знает, какие карты у Алисы, поскольку он видел только шифрограммы, зашифрованные алисиным клю\-чом. Алиса не знает, какие карты у Боба, поскольку она видела только шифрограммы, зашифрованные ключом Боба. Но это все в идеале. К сожа\-ле\-нию, требование коммутативности систем накладывает сильные ограни\-че\-ния на их выбор. Например, если мы пользуемся RSA (ключ Алисы - $a$, Боба - $b$), то для каждой карты Боба $t$ Бобу известны $t^b$ (он получает их от Алисы перед тем, как окончательно расшифровать), $t^{ab}$ (он отправляет их Алисе) и $t^a$ (он получает их от Алисы). При достаточной вычислительной мощности Боб может решить проблему дискретного логарифма и взломать код Алисы со всеми вытекающими последствиями. \par Именно поэтому между второй и третьей частями этой главы нет проти\-во\-ре\-чия. Абсолютно надежный протокол невозможен, зато возможен крип\-то\-гра\-фи\-чески надежный. \section{Пример работы византийского протокола} Пусть $n=4$, $m=1$. Может быть два принципиально различных слу\-чая: когда предатель - командир и когда предатель - один из заместителей. \begin{itemize} \item[Командир.] Желая ослабить наступление, командир приказывает двум замести\-те\-лям атаковать, а третьему - отступать. Согласно протоколу $BG(1)$, заместители рассылают друг другу копии приказа, используя прото\-кол $BG(0)$, то есть, посылают их прямым текстом. В итоге первый заместитель получает следующую сводку: \par \begin{supertabular}{|c|l|} \hline Командир&Атаковать! \\ \hline Второй зам.&Командир приказал атаковать! \\ \hline Третий зам.&Командир приказал отступать!\\ \hline \end{supertabular} \par Согласно $BG(1)$, первому заместителю следует атаковать. Аналогич\-ная ситуация складывается у второго заместителя. А вот сводка для третьего:\par \begin{supertabular}{|c|l|} \hline Командир&Отступать! \\ \hline Первый зам.&Командир приказал атаковать! \\ \hline Второй зам.&Командир приказал атаковать!\\ \hline \end{supertabular} \par Таким образом, третий заместитель тоже будет атаковать, несмотря на преступный приказ командира, и тем самым обеспечит согласо\-ван\-ность. \item[Заместитель.] Пусть предателем является третий заместитель. Желая запутать ос\-таль\-ных, он говорит, что командир приказал ему отступать, когда на самом деле приказ был атаковать. В таком случае первый заместитель получает следующую сводку: \par \begin{supertabular}{|c|l|} \hline Командир&Атаковать! \\ \hline Второй зам.&Командир приказал атаковать! \\ \hline Третий зам.&Командир приказал отступать! \\ \hline \end{supertabular} \par Сводка второго заместителя будет выглядеть так же. Как мы видим, гнусному предателю не удалось запутать доблестных воинов, которые смело пойдут в атаку. \end{itemize} Было бы интереснее, конечно, привести протокол $BG(2)$, но он, как известно, работает при $n \geq 7$, так что в нем участвует не менее $156$ сообщений. \end{document}