Доказательства с нулевым разглашением знания

From CryptoWiki
Jump to: navigation, search

Contents

Введение

Одна из основных задач криптографии представляет собой двустороннюю интерактивную игру, в которой один участник (доказывающая сторона) доказывает другому участнику (проверяющей стороне) истинность утверждения, не раскрывая сущности доказательства. В этом случае проверяющий не может самостоятельно оценить истинность утверждения, поскольку ему неизвестна информация, доступная доказывающему. Эта игра называется протоколом (системой) интерактивного доказательства или IP-протоколом (interactive proof — IP). Доказательство, осуществляемое IP-протоколом, можно назвать “секретным доказательством” (“proof in the dark”). Секретность этого доказательства состоит в том, что, во-первых, проверяющая сторона, убедившись в истинности доказываемого утверждения, не способна самостоятельно повторить доказательство, и, во-вторых, после завершения протокола никто из посторонних не способен понять ни одного сообщения, которыми обменивались доказывающая и проверяющая стороны.[M05]
Представим себе, что утверждение, которое необходимо доказать, не раскрывая сущности доказательства, является решением какой-либо знаменитой нерешенной математической задачи. В этом случае доказывающая сторона, опасающаяся плагиата, может пожелать скрыть технические детали доказательства от потенциально нечестного рецензента. Для этого она должна провести “секретное” доказательство, убедив рецензента (играющего роль проверяющей стороны в IP-протоколе) в корректности выводов, не давая никакой дополнительной информации.
Во многих реальных приложениях существуют намного более серьезные основания для проведения “секретных” доказательств. Как правило, IP-протоколы применяются для аутентификации сущностей. В отличие от обычных протоколов аутентификации, в которых пользователи ставят цифровые подписи, в IР-протоколе доказывающая сторона, подлежащая аутентификации, не желает, чтобы сообщения стали доступными кому-либо, кроме проверяющей стороны, и выполняет “секретную” аутентификацию. Кроме того, IP-протоколы часто применяются для того, чтобы доказать, что часть скрытой информации имеет определенную структуру. Это необходимо в некоторых секретных приложениях (например, при проведении электронных аукционов), в которых скрытый номер (лот) должен находиться в допустимом диапазоне (например, необходимо доказать, что х > у без раскрытия значений 20f.png и 21f.png, представляющих собой предложения цены).
Рассматривая IP-протоколы, необходимо изучить два вопроса.

  • Вопрос 1. Сколько информации получит проверяющая сторона в ходе интерактивного доказательства?
  • Вопрос 2. Сколько раундов должна выполнить доказывающая сторона, чтобы убедить проверяющего?

Идеальным ответом на первый вопрос был бы “нисколько”, или “нуль”. IP- протокол, обладающий таким свойством, называется протоколом с нулевым разглашением или ZK-протоколом (zero-knowledge — ZK). Второй вопрос важен не только для практических приложений, но и для теории вычислительной сложности, поскольку решение этой проблемы связано с получением более низкой оценки сложности.

История развития

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

Нулевое разглашение

Вычислительная модель

Обозначим основную модель протокола интерактивных доказательств через (Р,V), где Р — доказывающая (prover), а V — проверяющая сторона (verifier). Как правило, протокол (Р,V) предназначен для проверки принадлежности определенного предложения языку, заданному над алфавитом {0,1}*.
Пусть L — язык над алфавитом {0,1}*. Стороны Р и V получают образец хϵL, представляющий собой общие входные данные (common input). Доказательство принадлежности образца обозначается как (Р,V)(x). Обе стороны протокола связаны каналом связи, через который они обмениваются информацией.
Результат работы протокола записывается в следующем виде: (Р,V)(x) ϵ {Принять, Отклонить}.
Эти два значения означают, что проверяющая сторона либо подтверждает, либо опровергает утверждение хϵL, высказанное доказывающей стороной Р. Поскольку система (Р,V) является вероятностной, при каждом х результат (Р,V)(x) является случайной величиной, зависящей от общих входных данных х, закрытых входных данных (private input) пользователя Р и некоторых случайных входных данных (random input), общих для пользователей Р и Q.
Поскольку протокол (Р,V) является двусторонней игрой, естественно предположить, что каждая сторона стремится получить дополнительное преимущество. С одной стороны, доказывающая сторона Р должна быть заинтересована в результате принятия x, даже если оно не принадлежит L. Доказывающая сторона, руководствующаяся такой жульнической стратегией (cheating prover), обозначается как Р’. С другой стороны, проверяющая сторона V должна быть заинтересована в раскрытии информации о закрытых входных данных игрока Р. Проверяющая сторона, следующая такой нечестной стратегии (dishonest verifier), обозначается как V’.
Предположим, что на вопрос 1 существует идеальный ответ (Р,V) — протокол с нулевым разглашением, т.е. пользователь V (или V’) убеждается в корректности утверждения пользователя Р, не узнав ничего нового о его закрытых входных данных.
Для того чтобы протокол (Р,V) обладал этим свойством, необходимо ограничить вычислительную мощь пользователя V (или V’) полиномом, зависящим от размера его входной информации. Очевидно, что без этого ограничения нельзя гарантировать нулевое разглашение, поскольку пользователь V, обладающий неограниченными вычислительными ресурсами может самостоятельно раскрыть секретные входные данные пользователя Р. [FFS88]

Формальное определение протоколов интерактивного доказательства

Дадим определение протокола интерактивного доказательства. Пусть L — язык, заданный над алфавитом (0,1}*. IР-протокол (Р,V) называется системой интерактивного доказательства для языка L, если
10f.png
и
11f.png
где числа Ɛ и ϐ являются константами, удовлетворяющими условиям Ɛϵ(1/2;1], ϐϵ[0;1/2); Вероятностное пространство состоит из всех входных значений протокола (Р,V) и всех случайных входных данных пользователей Р и V.
Оценка (1) характеризует полноту протокола (Р,V). Величина Ɛ называется вероятностью полноты (completeness probability) протокола (Р,V). Это значит, что если х ϵ L, то проверяющая сторона V принимает предложение х с вероятностью, которая не меньше величины Ɛ.
Оценка (2) характеризует непротиворечивость (soundness) протокола (Р,V). Величина ϐ называется вероятностью противоречивости протокола (Р,V). Это значит, что если х не принадлежит L, то проверяющая сторона V принимает предложение х с вероятностью, не превышающей величины ϐ.
Рассмотрим введенные понятия на примере протокола 1, который называется протоколом интерактивного доказательства принадлежности подгруппе.
Протокол 1. Протокол интерактивного доказательства принадлежности подгруппе ОБЩИЕ ВХОДНЫЕ ДАННЫЕ:

  1. f: однонаправленная функция, определенная в группе 7f.png и удовлетворяющая гомоморфному условию:
  2. Для любых х, yϵ7f.png:f(x + y) = f(x) × f(y).

  3. X = f(z) для некоторого z ϵ 7f.png.

ЗАКРЫТЫЕ ВХОДНЫЕ ДАННЫЕ А:
z < n.
ЗАКЛЮЧЕНИЕ B:
X ϵ <f(1)>, тоесть элемент X порождается элементом f(1).

    Следующие шаги выполняются m раз.
  1. А генерирует число 7f.png, находит число Commit ← f(k) и посылает его B.
  2. B генерирует число Challenge {0,1} и посылает его А.
  3. А вычисляет число
    12f.png
    и посылает его B.
  4. B проверяет значение
    13f.png
    Если проверка завершается неудачно, B посылает отказ и прекращает работу протокола.[S05]

B принимает доказательство.

Идеальное нулевое разглашение

Пусть (Р,V) — IP-протокол для языка L. Для любого предложения х ϵ L выполнение протокола (Р,V)(х) приводит не только к выводу результата Принять, но и порождает стенограмму доказательства, в котором чередуются элементы стенограмм доказывающей и проверяющей стороны. Элементы стенограммы доказательства являются случайными величинами, зависящими от всех входных данных, включая случайные входные данные протокола (Р,V).
Очевидно, что доказательство (Р,V)(x) раскрывает любую информацию о закрытых входных данных пользователя Р только в том случае, если стенограмма доказательства допускает утечку информации.
Однако, если случайные величины в стенограмме доказательства являются равномерно распределенными (uniformly random) по соответствующему вероятностному пространству и не зависят от общих входных данных, то бессмысленно утверждать, будто они допускают утечку информации. Будем считать, что в этой ситуации (т.е. когда стенограмма доказательства состоит из равномерно распределенных случайных величин, не зависящих от общих входных данных) доказывающая сторона общается с проверяющей стороной на языке, не обладающем свойством избыточности (redundancy), т.е. имеющем наибольшую энтропию (highest possible entropy). Следовательно, не имеет значения, насколько умным (или мощным) является проверяющий пользователь. Даже изучая этот язык очень долгое время, он не сможет извлечь никакой дополнительной информации!
Итак протоколом доказательства с нулевым разглашением, согласно [SMP88], называется протокол доказательства, обладающий следующими свойствами:

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

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

Протоколы c нулевым разглашением

Простейший пример: пещера Али Бабы (Ali Baba)

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

Подробное описание

Протокол Фиата-Шамира (Fiat-Shamir)

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

Другой простейший пример: Кубик Рубика (Rubic's Cube)

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

Протокол на основе задачи об изоморфизме графов

Пусть дана пара графов G1=(U,E1) и G2=(U,E2), здесь U - множество вершин графа, а E1 и E2 - множества ребер. Задача состоит в нахождении перестановки вершин графа, которая переводит один граф в другой.
Подробное описание

Протокол Гуилоу-Куйсквуатера (Guillou-Quisquater или GQ)

Протокол Гуилоу-Куйсквуатера является расширением протокола Фиата-Шамира и в сравнении с ним имеет меньшее число сообщений, которыми необходимо поменяться сторонам, и более низкие требования к памяти, используемой для хранения секретов пользователей[MOV01]. Таким образом, данный протокол может быть использован в случаях, когда доказывающая сторона ограничена в вычислительных возможностях и доступной памяти.

Подробное описание

Протокол Шнорра (Schnorr)

Протокол Шнорра является альтернативой протоколам Фиата-Шамира и Гуилоу-Куйсквуатера. Безопасность данного протокола основана на проблеме дискретного логарифмирования[MOV01]. Данный протокол по сравнению с протоколом Фиата-Шамира имеет более низкие вычислительные требования и состоит только из 3-х этапов.

Подробное описание

Сравнение протоколов нулевого разглашения

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

  1. коммуникационные затраты - число сообщений, которыми участники протокола обмениваются, и общее число переданных бит;
  2. вычислительные затраты - число модульных умножений для обоих сторон;
  3. требования к памяти - необходимый для хранения секретных ключей объём памяти;
  4. гарантии безопасности - способность эффективно противодействовать противнику, который пытается раскрыть секретную информацию;
  5. небоходимость наличия доверенного центра - требование протокола наличия доверенного центра или его возможное отсутствие.

Сравним протоколы Фиата-Шамира, Гуилоу-Куйсквуатера и Шнорра по следующим параметрам:

  1. Вычислительные затраты. Протокол Фиата-Шамира требует на один-два порядка меньше, чем вычисление секретного ключа RSA. Так, при kt=20 и n размером в 512 бит, протокол Фиата-Шамира требует от 11 до 20 шагов, протокол Гуилоу-Куйсквуатера требует около 60 шагов, а неоптимизированный RSA -- 768.
  2. Предвычисления. В протоколе Шнорра доказывающая сторона в процессе взаимодействия должна выполнить лишь одно модульное умножение (возведение в степень может быть выполнено в процессе предвычислений), но проверяющая сторона в данном протоколе должна выполнить вычисления, которые значительно больше, требуемых в протоколах Фиата-Шамира и Гуилоу-Куйсквуатера.
  3. Требования к памяти и коммуникационные затраты. Протокол Гуилоу-Куйсквуатера даёт возможность уменьшения требований к памяти и коммуникационным затратам. В то время как в протоколе Фиата-Шамира такая возможность отсутствует[MOV01].
  4. Гарантии безопасности. Протокол Фиата-Шамира основывается на невозможности извлечения из числа корня по составному модулю. Протокол Гуилоу-Куйсквуатера требует невозможности получения из числа v корней по составному модулю. Протокол Шнорра требует невозможность вычисления дискретного логарифма по модулю простого числа.

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

Среди возможных атак на протоколы с нулевым разглашением можно выделить следующие:

  • персонация -- атака, когда один участник протокола пытается выдать себя за другого;
  • повтор -- атака, при которой при доказательстве утверждения используются сообщения из одного из предыдущих сеансов;
  • чередование -- атака, когда в протоколе используется чередование сообщений из предыдущих сеансов;
  • отражение -- атака, в ходе которой участнику протокола отправляются сообщения ранее полученные от него в рамках текущего активного взаимодействия;
  • вынужденная задержка -- атака, когда нарушитель перехватывает сообщение и передаёт его с некоторой задержкой;
  • атака с выбраным текстом -- атака, когда нарушитель пытается получить информацию о секрете путём передачи специальных значений параметров проверки.[BP03]

Глоссарий

Библиографический указатель

Перейти к списку литературы

Вернуться к оглавлению


Васецов А.С.,

Махонин В.Е.

Назад