Сайт о телевидении

Одна из лучших сторон современной криптографии - это ее прекрасная терминология. Можно создать сколько угодно панк-групп с названиями вроде Hardcore Predicate, Trapdoor Function или Impossible Differential Cryptanalysis. Однако есть термин, который превосходит все остальные. Это Zero Knowledge Proof - «доказательство с нулевым разглашением» .

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

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

История нулевого разглашения

Концепцию «нулевого разглашения» впервые предложили в 1980-х исследователи из MIT Шафи Гольдвассер (Shafi Goldwasser), Сильвио Микали (Silvio Micali) и Чарльз Рекофф (Charles Rackoff). Они изучали проблемы, связанные с интерактивными системами доказательства - теоретическими системами, в которых одна сторона («Prover» - Доказывающий), обменивающаяся сообщениями со второй стороной («Verifier» - Проверяющий), пытается убедить ее в истинности какого-либо математического утверждения.*

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

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

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

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

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

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

Пока наше обсуждение довольно абстрактно, так что давайте рассмотрим «реальный» пример (немного безумного) протокола с нулевым разглашением.

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

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

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

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

Но это приводит к проблеме.

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

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

Сумасшедшее техническое решение (с шляпами!)

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

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

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

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

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

1. Полнота (completeness ). Если Google говорит правду, то в итоге сможет убедить меня (по крайней мере, с высокой вероятностью).
2. Корректность (soundness ). Google может убедить меня в правильности решения только в том случае, если на самом деле говорит правду.
3. Нулевое разглашение (zero — knowledgeness ) . Я больше ничего не узнаю о решении Google.

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

Затруднения здесь вызывает третье свойство, но чтобы понять это, нам нужно провести очень странный мысленный эксперимент.

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

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

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

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

Понятия не имею, что здесь происходит, но мне показалось, что картинка вполне подходит.

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

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

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

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

К чему это все?

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

Мы только что показали, что если время течет не только вперед - точнее говоря, если Google может «перематывать» мое представление о времени - то Google может подделать действительный запуск протокола даже без информации о фактической раскраск e графа.

Какова с моей точки зрения разница между двумя вариантами протокола? Если рассматривать их статистическое распределение, разницы нет никакой - оба сообщают примерно одинаковый объем полезной информации.

Хотите - верьте, хотите - нет, но это доказывает кое-что очень важное.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Хорошо, и что же все это означает?

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

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

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

Доказательства для всех NP!

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

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

Этот результат одним махом - благодаря Голдрайху , Микали и Видждерсону - доказывает, что «эффективные» доказательства с нулевым разглашением существуют для широкого класса полезных утверждений, многие из которых гораздо более интересны, чем назначение частот сотовым сетям. Вы просто находите утверждение (в классе NP), которое хотите доказать, такое как наш приведенный выше пример хеш-функции, а затем преобразуете его в экземпляр проблемы 3-х цветов. После этого вы просто запускаете цифровую версию протокола с шляпами.

Подведем итоги

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

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

В других сообщениях я расскажу о некоторых из них - а именно эффективных доказательствах разных полезных утверждений. Я приведу некоторые примеры (из реальных приложений), где такие приемы были использованы. Также по запросу одного из читателей я расскажу, почему мне так не нравится протокол SRP (Secure Remote Password).

Примечания

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

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

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

Мэтью Грин (Matthew Green)

Пусть задана интерактивная система доказательства (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) -> т раз 4 Вычисляет граф \j/Ga и сравнивает: Н =\jfGa 5 Принимает доказательство тогда и только тогда, когда для Vm
Этот протокол действительно является протоколом с нулевым разглашением знаний, так как в случае изоморфных G0 ~ Gx участ-ник V не получает никакой информации, кроме изоморфизмов гра-фов G0 и G\ с какими-то их случайными перенумерациями, которые он мог бы получить и самостоятельно, выбирая случайный бит а и перенумеровывая случайным образом граф Ga .
3. Доказательство знания дискретного логарифма х числа X. Перед началом работы протокола задаются открытые величины: р,
q - простые числа, такие, что q\(p -1), элемент g е Z*, число X. До- ]. Базовые криптографические протоколы 31
называющему Р известна секретная величина x\xТаблица 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""> знание которых он должен доказать 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 >\
ные всем участникам: простые числа р, q, элементы у, 82^є для некоторых (/). Доказывающему Р известны сек-ретные величины 0С[,а2,...,а,. є Zq, такие, что для V/ у^ =
= (і^) " 1 > знание которых он должен доказать 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 М=і">/Ї, 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, ϐϵ}