Доказательства с нулевым разглашением, Zcash и Ethereum.

Содержание:

Содержание

  • 1 Определение
  • 2 Различные виды нулевого разглашения
  • 3 История развития
  • 4 Общая структура доказательств с нулевым разглашением
  • 5 Примеры 5.1 Пещера нулевого разглашения
  • 5.2 Гамильтонов цикл для больших графов
  • 6 Применение на практике
  • 7 Злоупотребления
      7.1 Проблема гроссмейстера
  • 7.2 Обман с несколькими личностями
  • 7.3 Обман, выполненный мафией
  • 8 Возможные атаки
      8.1 Атака на основе подобранного шифротекста
  • 8.2 Атака на мультипротокольную систему нулевого знания
  • 8.3 Атака с помощью квантового компьютера
  • 9 См. также
  • 10 Примечания
  • 11 Литература
  • Определение[править | править код]

    Доказательство с нулевым разглашением — интерактивный вероятностный протокол, который позволяет доказать, что доказываемое утверждение верно, и Доказывающий знает это

    доказательство, в то же время не предоставляя никакой информации о самом доказательстве данного утверждения[7]. Данный криптографический протокол должен обладать тремя свойствами:

    1. Полнота
      : если утверждение действительно верно, то Доказывающий убедит в этом Проверяющего с любой наперед заданной точностью.
    2. Корректность
      : если утверждение неверно, то любой, даже «нечестный», Доказывающий не сможет убедить Проверяющего за исключением пренебрежимо малой вероятности.
    3. Нулевое разглашение
      : если утверждение верно, то любой, даже «нечестный», Проверяющий не узнает ничего кроме самого факта, что утверждение верно[8].

    Доказательства с нулевым разглашением не являются доказательствами в математическом смысле этого термина, потому что есть некоторая небольшая вероятность, что обманом доказывающая сторона сможет убедить Проверяющего в ложном утверждении (ошибка корректности

    ). Иными словами, доказательства с нулевым разглашением — это вероятностные доказательства, а не детерминированные. Тем не менее, есть методы, позволяющие уменьшить ошибку
    корректности
    до пренебрежимо малых значений[9][10].



    Избавляемся от шляп (и машин времени)

    Конечно, на самом деле мы не хотим выполнять протокол с шляпами и даже у Google нет настоящей машины времени (наверное).

    Чтобы связать все вместе, нам сначала нужно перенести наш протокол в цифровой мир. Это требует, чтобы мы сконструировали цифровой эквивалент «шляпы» — что-то, что одновременно скрывает цифровое значение и при этом «привязывает» создателя к нему («обязывает»), чтобы он не мог передумать постфактум.

    К счастью, у нас есть идеальный инструмент для этого, который называется цифровой схемой обязательства. Схема обязательства позволяет одной стороне «выразить обязательство» для конкретного сообщения, сохранив его при этом в «секретном конверте», а затем позднее «раскрыть» конверт с обязательством, чтобы показать, что внутри. Обязательства можно создавать из раличных ингредиентов, включая (надежные) криптографические хеш-функции.***

    Со схемой обязательства у нас есть все, что нужно для электронного выполнения протокола с нулевым разглашением. Доказывающий сначала кодирует расцветку вершин как набор цифровых сообщений (например, с помощью чисел 0, 1, 2), а затем генерирует для каждого из них цифровые обязательства. Эти обязательства пересылаются Проверяющему. Когда Проверяющий оспаривает решение для какого-то ребра, Доказывающий просто обнародует значения для обязательств, соответствующих двум вершинам.

    Так мы устранили шляпы, но как доказать, что это протокол с нулевым разглашением?

    К счастью, теперь мы в цифровом мире, и нам не нужна реальная машина времени для доказательства утверждений об этом протоколе. Главная хитрость в том, чтобы указать, что протокол будет работать не между людьми, а между двумя разными компьютерными программами (или, выражаясь более формальным языком, вероятностными машинами Тьюринга).

    Теперь мы можем доказать следующую теорему. Если бы удалось создать компьютерную программу (для Проверяющего), извлекающую полезную информацию после участия в запуске протокола, можно было бы использовать с этой программой «машину времени», чтобы программа извлекла тот же объем полезной информации из «поддельного» запуска протокола, когда Доказывающий не предоставляет никакой информации.

    И, поскольку мы теперь говорим о компьютерных программах, очевидно, что перемотка времени вовсе не является экстраординарной возможностью. На самом деле, мы перематываем компьютерные программы все время. Возьмем для примера ПО для виртуальных машин с функцией создания снимков.


    Пример перемотки снимков виртуальных машин. Первоначальная виртуальная машина воспроизводится вперед, возвращается к первоначальному снимку, а затем выполняется другая ветвь.

    Даже если у вас нет хитрого ПО для виртуальных машин, любую компьютерную программу можно «перемотать» к более раннему состоянию, просто снова запустив ее с начала и передав ей в точности тот же ввод. Если ввод — включая все случайные числа — фиксирован, программа всегда будет следовать по одному и тому же пути выполнения. Вы можете перемотать программу, просто запустив ее с начала и «форкнув» ее выполнение по достижении некоторой желаемой точки.

    В конечном итоге мы получаем следующую теорему. Если существует какая-либо компьютерная программа Проверяющего, которая успешно извлекает информацию, интерактивно выполняя этот протокол с некоторым Доказывающим, мы можем просто использовать хитрость с перемоткой, чтобы выразить обязательство для случайного решения, а затем «обмануть» Проверяющего, перематывая программу, пока не пройдем испытание. Имеет место та же логика, что и выше: если бы такой Проверяющий преуспел в извлечении информации после выполнения реального протокола, то он мог бы извлечь тот же объем информации из симулированного протокола с перемоткой. Но поскольку симулированному протоколу не передается никакая информация, то и извлечь нечего. Следовательно, объем информации, которую Проверяющий может извлечь, равен нулю.

    Различные виды нулевого разглашения[править | править код]

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

    приводит к выводу результата
    Принять/Отклонить
    и также порождает стенограмму доказательства. Различные варианты нулевого разглашения могут быть определены путём формализации самого понятия и сравнения распространения информации различных моделей с протоколом следующими способами[11][12]:

    • Идеальный протокол нулевого разглашения
      — если случайные величины в стенограмме доказательства рассматриваемой модели являются равномерно распределенными и не зависят от общих входных данных[13]. Хорошей иллюстрацией будет пример Алисы и Боба в пещере.
    • Статистически нулевое разглашение
      [14] означает, что распределение не обязательно такое же, но они по крайней мере статистически близки[en], при этом статистическая разница есть незначительная функция[en][15].
    • С вычислительно нулевым разглашением
      называют такую модель, если не существует на данный момент такого эффективного алгоритма, который смог бы отличить распределение величин от распространения информации в идеальном протоколе[16].

    История развития[править | править код]

    В 1986 году в работе Сильвио Микали, Одеда Голдрейха[en] и Ави Вигдерсона было описано применение доказательств с нулевым разглашением для создания криптографических протоколов, которые должны обеспечивать «честное поведение»

    сторон, сохраняя при этом конфиденциальность[17].
    Шафи Гольдвассер
    Доказательство с нулевым разглашением было придумано и разработано следующими учёными: Шафи Гольдвассер, Сильвио Микали и Чарльзом Реккофом, и опубликовано ими в статье «Знание и сложность интерактивной системы с доказательством»[18] в 1989 году. Эта работа представила иерархию интерактивных систем с доказательством, основываясь на объёме информации о доказательстве, который необходимо передать от Доказывающего до Проверяющего. Ими так же было предложено первое доказательство конкретно поставленного доказательства с нулевым разглашением — квадратичного вычета по некоторому модулю m

    [19]. Впоследствии, дополнив свою работу, они были удостоены первой премии Гёделя в 1993 году[20].

    В дальнейшем криптосистема Гольдвассер — Микали, основанная на рассматриваемом интерактивном протоколе, являющаяся криптографической системой с открытым ключом, разработанная Шафи Гольдвассер и Сильвио Микали в 1982 году, является первой схемой вероятностного шифрования с открытым ключом, доказуемо стойкая при стандартных криптографических предположениях. Предложенная система была высоко оценена жюри: Гольдовассер и Микали стали лауреатами Премии Тьюринга за 2012 год[21], за создание криптосистемы с вероятностным шифрованием, отмеченная в номинации как новаторская работа, оказавшая существенное влияние на современную криптографию. Однако, криптосистема является неэффективной, так как порождаемый ею шифротекст может быть в сотни раз длиннее, чем шифруемое сообщение.

    Для доказательства свойств стойкости криптосистемы Голдвассер и Микали ввели понятие семантической стойкости[22][23].

    Общая структура доказательств с нулевым разглашением[править | править код]

    Каждый раунд, или аккредитация доказательства, состоит из трёх этапов. Схематично их можно изобразить следующим образом:

    • A ⇒ B {displaystyle ARightarrow B} : доказательство (witness)
    • A ⇐ B {displaystyle ALeftarrow B} : вызов (challenge)
    • A ⇒ B {displaystyle ARightarrow B} : ответ (response)

    Сначала A

    выбирает из заранее определённого непустого множества некоторый элемент, который становится её секретом — закрытым ключом. По этому элементу вычисляется, а затем публикуется открытый ключ. Знание секрета определяет множество вопросов, на которые
    А
    всегда сможет дать правильные ответы. Затем
    A
    выбирает случайный элемент из множества, по определённым правилам (в зависимости от конкретного алгоритма) вычисляет доказательство и затем отсылает его
    B
    . После этого
    B
    выбирает из всего множества вопросов один и просит
    A
    ответить на него (вызов). В зависимости от вопроса,
    А
    посылает
    B
    ответ[24]. Полученной информации
    B
    достаточно, чтобы проверить действительно ли
    А
    владеет секретом. Раунды можно повторять сколько угодно раз, пока вероятность того, что
    A
    «угадывает» ответы, не станет достаточно низкой. Такой подход называется также «разрезать и выбрать» («cut-and-choose»), впервые использованный в криптографии Михаэлем Рабином[25][26].



















    Примеры[править | править код]

    Пещера нулевого разглашения[править | править код]

    Пещера нулевого разглашения
    Основная статья: Пещера нулевого разглашения

    Впервые данный пример был написан в хорошо известной работе по доказательству с нулевым разглашением «Как объяснить протокол доказательства с нулевым разглашением вашим детям» Жан-Жаком Кискатером (англ.)русск.[27].

    В данном случае Пегги выступает в качестве Доказывающего утверждение, и Виктор — в качестве Проверяющего (в англоязычной литературе обычно используются наименование сторон Peggy

    от «Prover» и
    Victor
    от «Verifier»). Пегги знает магическое слово («ключ»), ввод которого позволяет открыть ей дверь между C и D. Виктор хочет узнать, действительно ли Пегги знает пароль, при этом Пегги не хочет выдавать сам пароль. Пещера имеет круглую форму, как представлено на рисунке. Для того чтобы решить проблему, они поступают следующим способом. Пока Виктор находится в точке А, Пегги идёт к двери, и после того, как она исчезает из виду, Виктор идёт к разветвлению, то есть в точку B, и кричит оттуда: «Пегги нужно выйти
    справа
    » или «Пегги нужно выйти
    слева
    ». Получаем каждый раз вероятность того, что Пегги не знает пароль, равна 50 %. Если же повторить процесс
    k
    раз, то вероятность будет 1 2 k {displaystyle {frac {1}{2^{k}}}} . При 20 же повторениях эта вероятность будет порядка 10−6, что является достаточным для справедливости предположения о том, что Пегги знает ключ[27].







    Если Виктор запишет все происходящее на камеру, то полученная видеозапись не будет являться доказательством для какой-либо другой стороны. Ведь они могли заранее сговориться, откуда будет выходить Пегги. Соответственно, она сможет найти выход, не зная при этом самого ключа. Существует ещё один способ: Виктор просто вырезает все неудачные попытки Пегги. Эти описанные выше действия доказывают, что пример с пещерой удовлетворяет свойствам: полноты, корректности и нулевому разглашению[28].

    Гамильтонов цикл для больших графов[править | править код]

    Граф додекаэдра с выделенным циклом Гамильтона.
    Этот пример был придуман Мануэлем Блюмом и описан в его работе в 1986 году[29]. Назовём проверяющую сторону Виктор, а доказывающую сторону Пегги. Допустим, Пегги известен гамильтонов цикл в большом графе G

    . Виктору известен граф
    G
    , но он не знает гамильтонова цикла в нём. Пегги хочет доказать Виктору, что она знает гамильтонов цикл, не выдавая при этом ни самого цикла, ни какой-либо информации о нём (возможно Виктор хочет купить информацию об этом гамильтоновом цикле у Пегги, но перед этим желает удостовериться, что Пегги действительно знает его).

    Для этого Виктор и Пегги совместно выполняют несколько раундов протокола:

    • Вначале Пегги создаёт граф H
      , изоморфный
      G
      . Преобразование гамильтонова цикла между изоморфными графами — тривиальная задача, поэтому если Пегги известен гамильтонов цикл в
      G
      , то она также знает гамильтонов цикл в порождаемом графе
      H
      .






    • Пегги передаёт граф H
      Виктору.
    • Виктор выбирает случайный бит b
      ∈ {displaystyle in } {0, 1}. Если
      b
      = 0, то Виктор просит Пегги доказать изоморфизм
      G
      и
      H
      , то есть предоставить взаимнооднозначное соответствие вершин этих двух графов. Виктор может проверить, действительно ли
      G
      и
      H
      изоморфны.










    • Если b
      = 1, то Виктор просит Пегги указать гамильтонов цикл в
      H
      . Для задачи изоморфизма графов на данный момент не доказана ни её принадлежность классу P {displaystyle P} , ни её N P {displaystyle NP} -полнота, поэтому будем здесь считать, что невозможно из гамильтонова цикла в
      H
      вычислить гамильтонов цикл в изоморфном
      G
      [29].






    В каждом раунде Виктор выбирает новый случайный бит, который неизвестен Пегги, поэтому, чтобы Пегги могла ответить на оба вопроса, нужно чтобы H

    был в самом деле изоморфен
    G
    , и Пегги должна знать гамильтонов цикл в
    H
    (а значит также и в
    G
    ). Поэтому после достаточного числа раундов, Виктор может быть уверен в том, что у Пегги действительно есть знание о гамильтоновом цикле в
    G
    . С другой стороны, Пегги не раскрывает никакой информации о гамильтоновом цикле в
    G
    . Более того, Виктору сложно будет доказать кому-либо ещё, что он сам или Пегги знают гамильтонов цикл в
    G
    [29].











    Предположим, что Пегги неизвестен гамильтонов цикл в G

    , но она хочет обмануть Виктора. Тогда Пегги необходим неизоморфный
    G
    граф
    G′
    , в котором она всё-таки знает гамильтонов цикл. В каждом раунде она может передавать Виктору либо
    H′
    — изоморфный
    G′
    , либо
    H
    — изоморфный
    G
    . Если Виктор попросит доказать изоморфизм графов, и ему был передан
    H
    , то обман не вскроется. Аналогично, если он просит показать гамильтонов цикл, и ему был передан
    H′
    . В таком случае вероятность того, что Пегги всё-таки обманет Виктора после
    k
    раундов, равна 1 2 k {displaystyle {frac {1}{2^{k}}}} , что может быть меньше любой заранее заданной величины при достаточном числе раундов[29].

















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

    для проверок изоморфизма и
    H′
    для проверок гамильтонова цикла. Таким образом без участия Пегги доказать, что она знает гамильтонов цикл, можно лишь доказав, что во всех раундах протокола выбирались действительно случайные биты[30].

    Происхождение нулевого разглашения

    До Голдвассера и других, большинство работ в этой области фокусировались на системах доказательства правильности. То есть, на случаях, когда злоумышленник — Испытатель пытается провернуть трюк с Контролёром, подсовывая ему ложное значение. Но Голдвассер, Микали и Ракофф рассмотрели противоположную сторону этой проблемы. Вместо того, чтобы беспокоится только об Испытателе, они спросили: что произойдёт, если вы не доверяете Контролёру?

    Особо их обеспокоила возможность утечки информации. Конкретно, они задались вопросом, сколько дополнительной информации получит Контролёр в ходе доказательства самого факта, что утверждение верно?

    Важно отметить, что это не просто теоретический интерес. Есть реальные, практические приложения, в которых эти вещи важны.

    Вот одно из них: представьте, что клиент в реальном мире хочет войти на веб-сервер, используя пароль. Стандартный подход к проблеме «в реальном мире» включает в себя хранение хэшированной версии пароля на сервере. Логин в такой системе рассматривается как вид «подтверждения», что хэш предоставленного пароля это выход хэширующей функции действующего пароля. И, что более важно, как «подтверждение» того, что клиент действительно знает пароль.

    Большинство систем в реальном мире реализуют это «подтверждение» наихудшим образом из возможных. Клиент просто передаёт оригинальный пароль на сервер, который повторно вычислят хэш пароля и сравнивает его с сохранённым значением. Проблема здесь очевидна: сервер получает мой пароль в самом притягательном для хакеров виде «чистый текст». А пользователь может только молится о том, что защита сервера не скомпрометирована.

    То, что предложили Голдвассер, Микали и Ракофф, стало надеждой на появление новых методов подтверждения. В случае полной реализации, доказательства с нулевым разглашением смогут дать подтверждение в описанной выше задаче. При этом не разгласив ни одного бита информации, которая соответствует тому, что «это утверждение верно».

    Пример из «реального мира»

    До сих пор мы разговаривали о довольно абстрактных вещах. Давайте пойдём вперёд и приведём реальный пример (слегка безумный) для протокола «нулевое разглашение».

    Чтобы мне было проще объяснить этот пример, давайте представим, что я магнат телекоммуникаций и нахожусь в процессе развёртывания новой сотовой сети. Моя сетевая структура представлена ниже на этом графе. Каждая вершина графа представляет собой мобильный передатчик, и соединяющие линии (грани) показывают места, где две соты перекрываются. В этих местах передатчики будут создавать друг другу помехи. Хорошо, что моя сетевая структура позволяет настроить каждую башню в одном из трёх частотных диапазонов, чтобы избежать такого влияния.

    Таким образом, задача развёртывания моей сети сводится к тому, чтобы назначить свою полосу для каждой башни таким образом, чтобы клетки не пересекались. Если мы используем цвета для отображения частотных полос, то можем быстро разработать одно решение для этой проблемы:

    Конечно, многие из вас уже заметили. То, что я описал здесь — только частный случай знаменитой теоретической проблемы. Она носит название «проблемы раскраски графа в три цвета «. Вы можете также знать об одной очень интересной особенности этой проблемы. Для некоторых графов очень трудно найти решение или даже определить, что такое решение существует. Задача раскраски графа в три цвета (и поиск ответа на вопрос, существует ли такое решение для данного случая), как известно, относятся к разряду NP-полных задач .

    Само собой разумеется, что вышеописанные игрушечные загадки решить просто. Но если бы это не было так просто? Например, представьте, что моя сеть сотовой связи была очень большой и сложной. В этом случае мне бы не хватило вычислительной мощности, чтобы найти решение. В этом случае, было бы желательно поручить решение проблемы кому-нибудь ещё. Тому, у кого достаточно вычислительной мощности. Например, я мог бы попросить Google решить эту задачу.

    Но есть одна проблема.

    Предположим, что Google уделит мне столько, сколько нужно вычислительных мощностей для того, чтобы найти решение правильной раскраски моего графа. Я, конечно, не собираюсь платить им, пока не буду уверен в том, что у них есть это решение. В то же время, Google не собирается предоставить мне копию решения до тех пор, пока я не оплачу её. Мы в тупике.

    В реальной жизни здравый смысл подсказывает нам ответ на эту дилемму, который включает в себя услуги юристов и эскроу-счета. Но здесь мы говорим не о реальной жизни, а о криптографии. И, если вы когда-нибудь читали работы криптографов, то уже знаете, что единственный способ найти решение проблемы — придумать полностью сумасшедшее техническое решение. Сумасшедшее техническое решение (со шляпами)

    Представим, что сотрудники Google проконсультировались у Сильвио Микали из MIT, а он расспросил своих коллег Оде Голдрих (Oded Goldreich) и Ави Виджерсон (Avi Wigderson). Посоветовавшись, они разработали протокол, который настолько красив, что даже не требует компьютеров. Будет использоваться большой склад с запасом цветных карандашей и бумаги. Ещё понадобится большое количество шляп.

    Рассмотрим, как это работает

    Сначала я войду в помещение склада и застелю пол бумагой, чтобы создать пространство для представления моей сотовой сети. Затем я покину склад. Google теперь может войти, перемешать коллекцию карандашей и выбрать три любых цвета (например, красный / голубой / фиолетовый, как в этом примере), и цвет, которым будет обозначено решение. Заметим, что какой конкретно цвет используется, значения не имеет.

    Перед тем, как покинуть склад, Google накрывает каждую вершину шляпой. Когда я вернусь, это всё, что я увижу:

    Очевидно, что такой подход отлично защитит секрет Google. Но это совсем не поможет мне. Возможно, Google заполняет цвета в случайном, а значит, в неправильном порядке. А может быть, они вообще не заполняли ничего.

    Чтобы убедить меня в том, что задача действительно решалась, Google даёт мне возможность «проверить» их результат раскраски графа. Я имею право выбрать, в случайном порядке, одну грань этого графа (то есть, по одной линии между двумя соседними шляпами). Google будет удалять эти две шляпы, показывая мне небольшую часть решения:

    Обратите внимание, что у моего эксперимента есть два возможных исхода:

    Если две показанные вершины имеют один и тот же цвет (или же вообще не окрашены!) тогда я точно буду уверен, что Google обманывает меня. В этом случае я не заплачу Google даже цента. Если две показанные вершины имеют различные цвета, значит, Google в этом случае не обманывает меня.

    Надеюсь, первое утверждение очевидно. Второе потребует более подробного объяснения. Проблема в том, что если даже эксперимент был успешным, Google по-прежнему может обманывать меня. Всё-таки, я заглянул всего лишь под две шляпы. Если существует E различных рёбер в графе, то Google с большой долей вероятности может предоставить ошибочное решение. Например, после одного теста они обманывают меня с вероятностью (E-1) / E (что для 1000 граней будет составлять 99.9%).

    К счастью, у Google есть ответ на этот вопрос. Мы просто запустим протокол снова!

    Мы берём чистую бумагу для создания новой копии графа. Google теперь берёт новую случайную перетасовку трёх цветных карандашей. Затем они заполняют граф верным решением, но используя новый случайный набор трёх цветов.

    Опять проводим операцию со шляпами. Я возвращаюсь, и в случайном порядке выбираю новые вершины. Ещё раз обратимся к логике, описанной выше. В этот раз, если всё пройдёт хорошо, я буду гораздо более уверен, что Google говорит мне правду. Это связано с тем, что, для того, чтобы обмануть меня, Google должно было повезти два раза.

    Такое событие может произойти — но его вероятность будет ещё ниже. Вероятность того, что Google одурачит меня два раза подряд, составляет (E-1) / E * (E-1) / E (или около 99.8% вероятности для нашего примера с 1000 граней).

    К счастью, мы не должны останавливаться на двух попытках. Мы будем пробовать снова и снова, пока не убедимся, что Google, с высокой долей вероятности, говорит правду.

    Я призываю вас не верить мне на слово. Опробуйте этот Javascript, и убедитесь в этом самостоятельно.

    Обратите внимание, что я никогда не уверен полностью, что Google честен – всегда остаётся крошечная вероятность, что они обманывают меня. Но, после большого количества итераций (E ^ 2, как в нашем случае) я в конце концов дойду до точки, в которой Google обманывает меня с пренебрежимо малой вероятностью – достаточной для применения на практике. После этого я спокойно могу отдать деньги Google.

    Важно, что Google в этом случае также защищён. Если я попытаюсь узнать что-либо, сохраняя и анализируя заметки между запусками протокола, то потерплю неудачу Это вызвано тем, что Google при каждой итерации использует цвета, выбранные в случайном порядке. Ограниченная информация, которую я могу получить, не даст мне ничего. Для меня не существует способа связать эти данные воедино.

    Что делает этот пример «нулевым разглашением»?

    Я пытаюсь убедить вас, что этот протокол не позволяет просочиться информации о решении Google. Но вам не нужно верить мне на слово! Первое правило криптографов заключается в том, чтобы никогда не верить таким вещам без доказательств.

    Голдвассер, Микали и Ракофф предложили три критерия, которым должен отвечать каждый протокол «нулевое разглашение». Неформально их можно описать так:

    Полнота. Если Google говорит мне правду, то я должен получить убедительные доказательства этого (доказательства с высокой вероятностью). Надёжность. Google может убедить меня только в том случае, если действительно говорит правду. «Нулевое разглашение» (этот критерий действительно так и называется). Я не должен узнать ничего больше, кроме полученного решения Google.

    Мы уже обсудили аргументы в пользу полноты. Протокол в конечном счёте убедит меня (с пренебрежимо малой вероятностью ошибки), если запустить его достаточное число раз. Надёжность тоже достаточно легко показать. Если Google попытается обмануть меня, я обнаружу это в подавляющем большинстве случаев.

    Самым сложным свойством осталось «нулевое разглашение». Чтобы разобраться в нём, сделаем довольно странный мысленный эксперимент.

    Применение на практике[править | править код]

    Теорема, гласящая, что для любой NP-полной задачи существует доказательство с нулевым разглашением, при этом, если использовать односторонние функции, можно создать корректные криптографические протоколы, была доказана Одедом Голдрейхом[en], Сильвио Микали и Ави Вигдерсоном[17][31]. То есть, можно доказать любому скептику, что обладаешь доказательством некоей математической теоремы, не раскрывая самого доказательства. Это тоже показывает, как может быть использован данный протокол в практических целях[11].

    Следующим методом, где может быть использовано доказательство с нулевым разглашением, является определением идентичности, при этом закрытый ключ у Пегги является так называемым «показателем идентичности», и, используя рассматриваемый протокол, можно доказать свою идентичность. То есть, можно доказать свою личность без использования различных физических устройств и данных (символов), таких как паспорта, различных снимков человека (сетчатки глаза, пальцев рук, лица и т. д.), а принципиально другим образом[32]. Однако, он имеет ряд недостатков, которые могут быть применены для обхода защиты. Описанный выше метод был впервые предложен Амосом Фиатом[en], Ади Шамиром и Уриэлем Фейге в 1987 году[33].

    Также доказательства с нулевым разглашением могут быть использованы в протоколах конфиденциального вычисления, которые позволяют нескольким участникам убедиться в том, что другая сторона следует протоколу честно[17].

    zk-SNARKS

    Технология zk-SNARK уменьшает размер доказательств и объем вычислений, необходимых для их проверки. Она может доказать, что условия для действительной транзакции были выполнены, не раскрывая какой-либо важной информации о задействованных адресах или ценностях.

    zk-SNARK преобразует содержимое транзакции, которое необходимо проверить, в доказательство того, что два полиномиальных продукта равны, в сочетании с гомоморфным шифрованием и другими передовыми методами для защиты скрытой суммы транзакции при выполнении проверки.

    Одна из ошибок текущей реализации zk-SNARK заключается в том, что параметры, отвечающие за проверку, могут быть взломаны и тогда вся сеть столкнется с разрушительными последствиями. Возможные решения включают использование современных технологий, таких как Intel SGX и ARM TrustZone. В технологии Intel SGX закрытый ключ остается в безопасности, даже если приложение, операционная система, BIOS или VMM скомпрометированы. Кроме того уже используются инновации в криптографии с нулевым знанием — это ZK-STARKs (масштабируемые прозрачные аргументы знания с нулевым знанием).

    Согласно техническому документу zk-STARK, он является первой системой, которая выполняет проверку блокчейна, не полагаясь ни на какие параметры доверия, в то время как скорость вычислений экспоненциально увеличивается с увеличением числа вычислительных данных. Он не опирается на криптосистемы с открытым ключом, и более простые предположения делают его теоретически более безопасным, поскольку его единственное предположение о шифровании состоит в том, что хэш-функции (такие, как SHA2) непредсказуемы.

    Злоупотребления[править | править код]

    Предложено несколько способов злоупотребления доказательством с нулевым разглашением, которые используют те или иные слабые стороны протокола:

    Проблема гроссмейстера[править | править код]

    Основная статья: Проблема гроссмейстера

    В данном примере некоторая сторона может доказать владение секретом, не обладая им на самом деле или, другими словами, может имитировать то лицо, которому на самом деле принадлежит секрет[34]. В настоящее время предложен способ решения проблемы Томасом Бетом[de] и Иво Десмедтом[en][35].

    Обман с несколькими личностями[править | править код]

    Основная статья: Обман с несколькими личностями

    Если сторона сможет создать несколько секретов, то соответственно она также сможет создать «несколько личностей», одну из которых никогда пусть не будет использовать. Такая возможность позволяет, например, совершить преступление и безнаказанно скрыться. Затем, во время совершения преступления, сторона идентифицирует себя никогда не используемой личностью. После преступления личность никогда больше не используется. Таким образом, выследить преступника практически невозможно. Данное злоупотребление обходится, если заранее не допустить возможность создания ещё одного секрета[36].

    Обман, выполненный мафией[править | править код]

    Основная статья: Обман, выполненный мафией

    Ещё один пример, когда одна сторона выдает себя за другую. Пусть имеется 4 участника: A

    ,
    B
    ,
    C
    ,
    D
    . Причём
    B
    и
    С
    сотрудничают между собой («принадлежат одной мафии»).
    А
    доказывает свою личность
    B
    , а
    С
    хочет выдать себя за
    A
    перед
    D
    .
    B
    владеет рестораном, принадлежащим мафии,
    С
    — также представитель мафии,
    D
    — ювелир.
    A
    и
    D
    не знают о предстоящем мошенничестве. В момент, когда
    A
    готов заплатить за обед и идентифицировать себя перед
    B
    ,
    B
    извещает
    С
    о начале мошенничества. Это возможно благодаря наличию радиоканала между ними. В это время
    С
    выбирает бриллиант, который хочет купить, и
    D
    начинает идентифицировать личность
    С
    , который выдает себя за
    A
    .
    С
    передаёт протокольный вопрос к
    B
    , а тот в свою очередь, задаёт его
    А
    . Ответ передаётся в обратном порядке. Таким образом
    А
    заплатит не только за обед, но и за дорогой бриллиант. Как видно из вышеописанного, существуют определённые требования для подобного мошенничества. Когда
    А
    начинает доказывать свою личность перед
    B
    , а
    С
    — перед
    D
    , действия
    B
    и
    С
    должны быть синхронизированы. Данное злоупотребление тоже разрешимо. Например, если в магазине ювелира будет клетка Фарадея, то «мафиози» не смогут обмениваться сообщениями[37].

































































    Вместо итогов

    Конечно, сразу начать использовать этот протокол на практике было бы безумно глупо. Его вычислительная стоимость будет включать в себя общий размер первоначального заявления и свидетельства, плюс стоимость перевода задачи в граф, и ещё E ^ 2 запусков протокола, которые необходимы для того, чтобы убедиться в правильности решения. Теоретически это «эффективно», но так как общая стоимость доказательства будет многочленом от длины входа, на практике это не применимо.

    Так что мы пока что доказали только то, что такие доказательства возможны. Осталось найти такие доказательства, которые являются достаточно практичными для реального использования.

    Примечания

    * Формально, целью интерактивного доказательства является убеждение Контролёра, что определённая строка принадлежит какому-либо языку. Обычно Испытатель в задачах имеет неограниченную мощность, а Контролёр ограничен в возможности расчётов.

    ** Этот пример основан на оригинальном решении Голдвассера, Микали и Ракофф, и учебном примере с использованием шляп, который разработал Сильвио Микали.

    ****** Простой пример обязательства может быть построен с использованием примера хэширующей функции. Для создания обязательства значения «x» мы просто генерируем некоторую (достаточно длинную) строку случайных чисел, которую назовём «соль», и выходное обязательство C = хэш (соль || x). Чтобы открыть обязательство, вы просто открываете «x» и «соль». Любой желающий может проверить, что первоначальное обязательство действует, пересчитав хэш повторно. Это безопасный метод при некоторых, умеренно сильных, предположениях о самой функции.

    Пусть задана интерактивная система доказательства (P,V,S). В определении интерактивной системы доказательства ранее не предполагалось, что V может быть противником (предполагалась только возможность существования нечестного участника Р»). Но V может оказаться противником, который хочет выведать у Р какую- либо новую полезную информацию об утверждении S. В этом слу-чае Р может не хотеть, чтобы это случилось в результате работы протокола интерактивной системы доказательства. Таким 28 Запечников С. В. Криптографические протоколы и их прішеиеиие образом приходим к идее протокола доказательства с нулевым раз-глашением знания (zero-knowledge proof). Нулевое разглашение зна-ния подразумевает, что в результате работы протокола интерактивной системы доказательства V не увеличит свои знания об утвер-ждении S, или, другими словами, не сможет извлечь никакой информации о том, почему S истинно. Как и ранее, в протоколе предварительно формулируется неко-торое утверждение S, например о том, что некоторый объект w об-ладает свойством L: we L. В ходе протокола Р и V обмениваются сообщениями. Каждый из них может генерировать случайные числа и использовать их в своих вычислениях. В конце протокола V дол-жен вынести свое окончательное решение о том, является ли S ис-тинным или ложным. Цель Р всегда состоит в том, чтобы убедить V в том, что S ис-тинно, независимо от того, истинно ли оно на самом деле или нет, т. е. Р может быть активным противником, а задача V — проверять аргументы Р. Цель участника V заключается в том, чтобы вынести решение, является ли S истинным или ложным. Как и ранее, V имеет полиномиально ограниченные вычислительные возможности, а именно время его работы ограничено некоторым полиномом от длины доказываемого утверждения: tРассмотрим теперь примеры протоколов доказательства с нулевым разглашением знания. 1. «Задача о пещере Али-Бабы». Имеется пещера, план которой показан на рис. 1.2. Пещера имрет дверь с секретом между точками С и D. Каждый, кто знает волшебные слова, может открыть эту дверь и пройти из С в D или наоборот. Для всех остальных оба хода пещеры ведут в тупик. Пусть Р знает секрет пещеры. Он хочет доказать V знание этого секрета, не разглашая волшебные слова. Вот протокол их общения: V находится в точке А, Р заходит в пещеру и добирается либо до точки С, либо до точки D После того как Р исчезает в пещере, V приходит в точку В, не зная, в какую сторону пошел Р V зовет Р и просит его выйти либо из левого, либо из правого коридора пещеры согласно желанию V, Р выполняет это, открывая при необходимости дверь, если, конечно, он знает волшебные слова, Р и V повторяют шаги (1) — (5) п раз.

    После п раундов протокола вероятность сократится до 1/2″. 2. Доказательство изоморфизма графов. Р хочет доказать V изо-морфизм графов Go и Gb ПустьG, = (p(G0):G0 = G, где ф — пре-образование изоморфизма, т — мощность множества N вершин графов. В табл. 1.4 приведен протокол доказательства данного утвер-ждения. Поясним строение этого протокола. На шаге (1) участник Р создает случайный граф Я, изоморфный G. На шаге (2) участник V, выбирая случайный бит а = {0Д}, тем самым просит доказать, что Н ~G0 либо что Н « Gj. На шаге (3) участник Р посылает участни-ку V преобразование |/, которое он строит таким образом, что при а = 1 в результате применения этого преобразования к графу Gu по-лучается граф F1 = TtG, = Н. а при а = 0 в результате применения этого преобразования к графу Ga получается граф F0 = зо Запечников С. В. Криптографические протоколы и их применение = 7i((p(G0))~7iG] = #, На шаге (4) участник V, выполняя проверку равенства графов, тем самым определяет, выполнено ли условие Н = Fa. Шаги (1) — (4) повторяются т раз. Если во всех т раундах этого протокола результат проверки оказывается положительным, V принимает доказательство. Таблица 1.4. Протокол доказательства изоморфизма графов Р V 1 % — случайная перестановка вершин, вычисляет H = nGl 2 f п, если (а -1), V = 1 / ч 1 л о ф, если (а = 0) -&gt, т раз 4 Вычисляет граф j/Ga и сравнивает: Н =jfGa 5 Принимает доказательство тогда и только тогда, когда для Vm Этот протокол действительно является протоколом с нулевым разглашением знаний, так как в случае изоморфных G0 ~ Gx участ-ник V не получает никакой информации, кроме изоморфизмов гра-фов G0 и G с какими-то их случайными перенумерациями, которые он мог бы получить и самостоятельно, выбирая случайный бит а и перенумеровывая случайным образом граф Ga . 3. Доказательство знания дискретного логарифма х числа X. Перед началом работы протокола задаются открытые величины: р, q — простые числа, такие, что q(p -1), элемент g е Z*, число X. До- ]. Базовые криптографические протоколы 31 называющему Р известна секретная величина xxТаблица 1.5. Протокол доказательства знания дискретного логарифма Р V I r&RZ М = g (mod р) 2 А. Доказательство знания представления числа у в базисе (zero- knowledge proof of knowledge of у representation). Перед началом работы протокола задаются открытые величины, известные всем уча-стникам: простые числа р, q, элементы y,gvg2,…, gk Є Gq. Доказы-вающему P известны секретные величины ара 2,…,ake ZQ: у = = 8і» » 8г1″»&gt, знание которых он должен доказать V, не разгла-шая самих этих величин. Протокол представлен в табл. 1.6. Таблица 1.6. Протокол доказательства знания представления числа в базисе Р V 1 rl.r2,…,rk. ЄІ{ Zq, 2 5. Доказательство знания представления множества чисел в соответствующих базисах (zero-knowledge proof of knowledge of equality of representation of all y(j) in the respective bases). Перед началом работы протокола задаются открытые величины, извест- W I &gt, ные всем участникам: простые числа р, q, элементы у, 82^є для некоторых (/). Доказывающему Р известны сек-ретные величины 0С[,а2,…,а,. є Zq, такие, что для V/ у^ = = (і^) » 1 &gt, знание которых он должен доказать V, не разглашая самих этих величин. В табл. 1.7 приведен протокол, который решает эту задачу. Таблица 1.7. Протокол доказательства знания множества чисел в соответствующих базисах Р V 1 rvr21…lrkeR ля У/ 2 (АиП«іТ-(ьТ- 6. Доказательство знания мультипликативной связи «депониро-ванных» величин (zero-knowledge proof of knowledge of multiplicative rela-tion between committed values). Элемент X = gx циклической подгруп-пы простого порядка, в которой задача дискретного логарифмирования считается вычислительно-сложной, называется депонированной вели-чиной (committed value), представляющей секретную величину х. Пусть d — неизвестный элемент, такой, что h = gd . Перед началом работы протокола задаются открытые величины: простые числа р, q, элементы А, В, С Є Gq . Доказывающему Р известны секретные величины a, a, b, Ь, с, с, такие, что с = ab, A = gah» В = gbhb, С = gche. Знание их он и должен доказать V, не разглашая самих величин. В табл. 1.8 при-веден протокол такого доказательства. Таблица 1.8. Протокол доказательства знания мультипликативной связи депонированных величин Р V 1 М=і»&gt,/Ї, j Mt = gx-h* ¦ M2= Bx ¦ h»1 2 =CK-M2 разглашением знания Таблица 1.9. Структура протоколов доказательства с нулевым P S: x є L- доказываемое утверждение, h — dp, общедоступные параметры и величины, s — секретные данные дока-зывающего о том, почему S истинно, г- случайное число V 1 rp- случ., 2 rv — случай-ное число, с = ЛМ Обобщим рассмотренные примеры и сформулируем ряд определений. В общем виде протокол интерактивного доказательства с ну-левым разглашением знания (табл. 1.9) состоит из четырех шагов: Окончание табл. 1.9 Р S: хе L- доказываемое утверждение, h — др. общедоступные параметры и величины, s — секретные данные дока-зывающего о том, почему S истинно, г — случайное число V 3 R = f3(C,x) 4 доказывающий передает проверяющему так называемое сви-детельство (witness -W)- результат вычисления однонаправленной функции от секретной величины, знание которой он доказывает, проверяющий посылает ему случайный запрос, доказывающий отвечает на этот запрос, причем ответ зависит как от случайного запроса, так и от секретной величины, но из него вычислительно невозможно получить эту секретную величину, получая ответ, V проверяет его соответствие «свидетельству», переданному на первом шаге. Рассмотрим основные принципы построения доказательств с ну-левым разглашением знания: что подразумевает свойство нулевого разглашения знания. В теории доказательств с нулевым разглашением знания Р и V рассматриваются как «черные ящики» (рис. 1.3). Пусть тр }, }Пу } — совокупность всех сообщений, передаваемых от Р к V (соответственно от У к Р), каждое из которых является слу-чайной величиной, и, таким образом, {x,h,rv,{mp},{mv}} = = viewpy, ϐϵ}

    Возможные атаки[править | править код]

    Атака на основе подобранного шифротекста[править | править код]

    Основная статья: Атака на основе подобранного шифротекста

    Данная атака осуществима при использовании неинтерактивного метода взаимодействия в протоколе нулевого разглашения.

    При использовании такого протокола возникает несколько проблем. Во-первых, нужно решить, как нужно осуществлять взаимодействие, и при этом должны быть сохранены фундаментальные особенности самого протокола: полнота, корректность и «нулевое разглашение». Помимо того, что можно достаточно просто доказать нулевое знание другой стороне, если можно прослушивать канал, то есть столкнуться с проблемой гроссмейстера.

    Так вот сама атака заключается в следующем: злоумышленник, используя сложность доказательства обладанием знания, включает «атакующий» шифротекст, подсовывая его в кучу других шифротекстов, которые должны быть расшифрованы. Данная атака называется «playback» атака[38].

    Возможное решение основано на работе Мони Наора[en] и Моти Юнга[en], которая заключается в следующем: Доказывающий и Проверяющий шифруют сообщения публичным ключом, это приводит к тому, что описанная выше атака перестает работать[39].

    Атака на мультипротокольную систему нулевого знания[править | править код]

    Тида и Ямамото предложили такую реализацию протокола нулевого знания, которая значительно повышает скорость доказательств обладанием нулевым знанием при одновременном доказательстве сразу нескольких утверждений и, как следствие, производительность всей системы в целом[40]. Ключевой особенностью является ограничение на количество итераций для доказательства. Как было показано в работе К. Пэна[41], данный алгоритм оказался полностью неустойчивым к следующей атаке. Используя несколько правильно подобранных итераций, злоумышленник может пройти верификацию и нарушить главные положения о протоколе. Причём было показано, что данная атака всегда осуществима на такую систему.

    Атака с помощью квантового компьютера[править | править код]

    В 2005 году Джоном Ватрусом[en] было показано[источник не указан 1676 дней

    ] , что не все системы с нулевым знанием являются устойчивыми к атакам с помощью квантового компьютера. Однако было доказано, что можно всегда построить такую систему, которая будет устойчива против квантовых атак, в предположении, что существуют квантовые системы с «сокрытием обязательств»[42].

    Мысленный эксперимент с машинами времени

    Во-первых, давайте начнём с сумасшедшего предположения. Представим, что инженеры Google вовсе не так умны, как люди думают о них. Они работают над этой проблемой неделю за неделей, и им никак не удаётся найти решение. За двенадцать часов до окончания дедлайна в Google впадают в отчаяние. Они решают обмануть меня, и говорят, что у них есть раскраска для графа (хотя на самом деле её у них нет).

    Их идея состоит в том, чтобы заглянуть в мастерскую GoogleX и позаимствовать на время прототип машины времени от Google. Первоначальным планом было отправиться на несколько лет назад и использовать дополнительное рабочее время на поиск новых решений проблемы. К сожалению, как и в случае с многими другими прототипами Google, машина времени имела ряд ограничений. Самое важное: она может отправиться во времени назад только на четыре с половиной минуты.

    Таким образом, отпадает использование машины времени для увеличения времени на выполнение работы. Но всё-таки, оказалось, что эта весьма ограниченная технология может использоваться, чтобы обмануть меня.

    Я действительно не знаю, что здесь происходит. Но кажется, это кстати.

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

    Предположим, я снимаю пару шляп и обнаруживаю две вершины одного и того же цвета. Если протокол реализован обычным образом, Google в этом случае потерпит фиаско. Но мы пользуемся машиной времени. Всякий раз, когда Google находит себя в неловком положении, он просто исправляет эту ситуацию. То есть, специально назначенный сотрудник Google дёргает рубильник, время перематывается назад на четыре с половиной минуты, и команда Google раскрашивает граф совершенно новым случайным решением. После этого они перематывают время вперёд и пробуют снова.

    По сути, машина времени позволяет Google ‘починить’ любой неудачный вход в протокол таким образом, чтобы я ничего не заподозрил. Так как плохие результаты будут происходить только в 1/3 случаев, ожидаемое время выполнения протокола (с точки зрения Google) только незначительно больше, чем в случае честного выполнения протокола. С моей точки зрения, я даже не знаю, что эти путешествия во времени происходят.

    Этот последний пункт является наиболее важным. С моей точки зрения, я одинаково взаимодействую с протоколом, есть машина времени или её нет. И всё же, стоит отметить ещё раз — в версии с машиной времени Google не имеет абсолютно никакой информации о том, как нужно раскрасить граф.

    И что же из этого следует?

    То, что мы только что показали — теоретический пример. В мире, где время бежит только вперёд, и никто не может обмануть меня с машиной времени, протокол с использованием шляп работает правильно. После E ^ 2 раундов его запуска я должен убедиться (не полностью, но с пренебрежимо малой вероятностью обмана), что граф окрашен правильно и Google обеспечил верную информацию.

    Если же временем можно манипулировать (в частности, если Google может ‘перемотать время’), то он может подделать протокол, даже если вообще не имеет информации о том, как должен быть окрашен граф.

    С моей точки зрения, какая разница между этими двумя протоколами? Они имеют одинаковое статистическое распределение и передают одинаковое количество полезной информации.

    Верьте или не верьте, это доказывает нечто очень важное.

    В частности, предполагается, что я (Контролёр) (Verifier) имею какую-то стратегию, которая позволит ‘извлечь’ полезную информацию о том, как Google производит окрашивание, в случае запуска честного протокола. Тогда моя стратегия должна так же хорошо работать в том случае, если меня дурачат с машиной времени. Запуски протокола, с моей точки зрения, статистически идентичны. Я физически не могу показать разницу.

    Таким образом, полностью идентично количество информации, которое я получу в ‘реальном эксперименте’ и ‘эксперименте с машиной времени’. Количество информации, которое Google вкладывает в случае эксперимента с ‘машиной времени’, в точности равно нулю. Следовательно, даже в реальном мире не произойдёт утечки информации. Осталось только показать, что у компьютерщиков есть машина времени (тсс, это секрет).

    Как избавиться от шляп и машин времени

    Конечно, на самом деле мы не хотели бы запускать протокол, пользуясь шляпами. И даже у Google (скорее всего) нет настоящей машины времени.

    Чтобы связать все эти вещи вместе ,нам нужно перенести этот протокол в цифровой мир. Для этого нам потребуется цифровой аналог ‘шляпы’: то, что скрывает цифровое значение, и в то же время ‘связывает’ значение и его создателя (создавая ‘обязательство’), таким образом, чтобы он не мог изменить своё мнение.

    К счастью, у нас есть прекрасный инструмент для этого приложения. Он называется цифровой схемой обязательства (digital commitment scheme). Схема обязательства позволяет одной из сторон создать для сообщения ‘обязательство’, сохраняя при этом его в секрете, а позже открыть ‘обязательство’, чтобы посмотреть, что внутри. Они могут быть построены из различных компонентов, в том числе из сильных криптографических функций хэширования.

    Получив схему обязательства, мы собрали все компоненты, чтобы запустить в электронном виде протокол нулевого разглашения. Испытатель сначала кодирует окраску вершин в виде набора цифровых сообщений (например, числами 0, 1, 2), затем генерирует цифровые обязательства для каждой. Эти обязательства пересылаются для Контролёра. Когда Контролёр открывает один край, Испытатель показывает значения для обязательств, которые соответствуют двум вершинам.

    Так нам удалось избавиться от шляп. Но как мы докажем, что этот протокол имеет нулевое разглашение?

    Но мы ведь сейчас находимся в цифровом мире. Поэтому нам не нужна машина времени, чтобы подтвердить то, что протокол работает. Ключевая хитрость заключается в том, что протокол будет работать не между двумя людьми, а между двумя различными компьютерными программами (или, говоря более формально, двумя вероятностными машинами Тьюринга (probabilistic Turing machines.)

    Сейчас мы можем доказать следующую теорему: если Контролёр собирается извлечь полезную информацию при обычном запуске протокола, он получит то же количество полезной информации, что и при ‘обманном’ запуске протокола, где Испытатель не вложил никакой информации с самого начала.

    Мы с вами говорим о компьютерных программах, а они умеют ‘возвращаться назад во времени’. Например, рассмотрим возможность использования виртуальной машины, которая умеет делать моментальные снимки. Пример ‘перемотки времени’ с использованием виртуальных машин. Первоначально виртуальная машина идёт по одному пути, возвращается к исходному состоянию, затем выполнение разветвляется на новый путь.

    Даже если не рассматривать виртуальные машины, любую компьютерную программу можно ‘перемотать’ к предыдущему состоянию, просто запустив программу с самого начала и послав на вход те же самые данные. При условии, что входы, (в том числе ввод случайных чисел), фиксированы, программа всегда будет следовать по одному и тому же пути выполнения. Так мы можем перемотать программу, запустив её со старта и ‘разветвив’ её выполнение, когда программа достигнет некоторой нужной точки.

    В конечном счёте, то, что мы получаем, можно представить в виде теоремы. Если для Контролёра существует компьютерная программа, которая успешно извлекает полезную информацию от Испытателя (интерактивно работая с протоколом), то Испытатель может использовать трюк с перемоткой программы, подсовывая Контролёру случайные решения. Используется логика, которую мы уже применяли выше: если Контролёр успешно может извлечь информацию, запустив реальный протокол, значит, он получит то же количество информации, запустив поддельный протокол, основанный на перемотке программы назад. Но так как поддельный протокол не передаёт полезных данных, нет никакой информации, которую можно извлечь. Таким образом, информация, которую может извлечь Контролёр, всегда равняется нулю.

    Что же из этого всего следует?

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

    В то же время, протокол имеет нулевое разглашение. Чтобы доказать это, мы показали, что программа, которую запускает Контролёр для извлечения информации, будет в состоянии извлечь данные из программы, в которой нет осмысленных данных. Это приводит к очевидному противоречию, которое говорит нам, что протокол в любой ситуации не имеет утечек информации.

    Это даёт нам важные преимущества. Так как любой может создать поддельную запись протокола, (как в примере с Google, когда они пытались убедить меня, что у них есть решение), я не могу переиграть запись протокола, чтобы доказать свою правоту кому-либо ещё (например, судье). Судья скажет, что не уверен в том, что запись сделана честно и не отредактирована (как в примере с Google и использованием машины времени). Это означает, что стенограмма протокола сама по себе не содержит никакой информации. Протокол имеет смысл только, если я сам принимал участие, и могу быть уверенным, что всё происходило в реальном времени.

    Примечания[править | править код]

    1. Goldreich, 2013.
    2. 12
      Шнайер, 2002, pp. 87—92.
    3. Goldwasser, Micali, Rackoff, 1989, pp. 186—189.
    4. Santis, Micali, Persiano, 1988.
    5. Blum, Feldman, Micali, 1988.
    6. Шнайер, 2002, pp. 90—91.
    7. Blum, 1988, p. 1444.
    8. Menezes et al, 1996, pp. 406—408.
    9. Шнайер, 2002, pp. 86—89.
    10. Goldwasser, Micali, Rackoff, 1989, pp. 188—189.
    11. 12
      Шнайер, 2002, pp. 91—92.
    12. Мао, 2005, pp. 683—696.
    13. Мао, 2005, pp. 684—688.
    14. Sahai, Vadhan, 2003.
    15. Мао, 2005, p. 696.
    16. Мао, 2005, pp. 692—696.
    17. 123
      Goldreich, Micali, Wigderson, 1986.
    18. Goldwasser, Micali, Rackoff, 1989.
    19. Goldwasser, Micali, Rackoff, 1989, pp. 198—205.
    20. Goldwasser, Micali and Rackoff Receive Gödel Prize in 1993 (неопр.)
      (недоступная ссылка). ACM Sigact (1993). Архивировано 8 декабря 2015 года.
    21. Goldwasser, Micali Receive ACM Turing Award for Advances in Cryptography (неопр.)
      (недоступная ссылка). ACM. Дата обращения 13 марта 2013. Архивировано 16 марта 2013 года.
    22. Goldwasser, Micali, 1982.
    23. Мао, 2005, pp. 524—528.
    24. Мао, 2005, pp. 678—682.
    25. M.O.Rabin.
      Digital signatures. — Foundations of Secure Computation. — New York: Academic Press, 1978. — С. 155—168. — ISBN 0122103505.
    26. Шнайер, 2002, pp. 87—89.
    27. 12
      Quisquater et al, 1990.
    28. Шнайер, 2002, pp. 87—88.
    29. 1234
      Blum, 1988.
    30. Шнайер, 2002, pp. 89—90.
    31. Goldreich, Micali, Wigderson, 1987.
    32. Шнайер, 2002, p. 92.
    33. Fiat, Shamir, 1987.
    34. Шнайер, 2002, pp. 92—93.
    35. Beth, Desmedt, 1991.
    36. Шнайер, 2002, pp. 93—94.
    37. Шнайер, 2002, p. 93.
    38. Rackoff, Simon, 1992.
    39. Naor, Yung, 1990.
    40. Chida, Yamamoto, 2008.
    41. Peng, 2012.
    42. Watrous, 2006.


    Понравилась статья? Поделиться с друзьями:
    Добавить комментарий