Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
«Доказывающая», которую мы назовем Пикара, знает решение. «Проверяющий», которого мы назовем Вивалес, — это тот, кого нужно убедить в том, что Пикара знает решение, не дав ему при этом даже смутного представления о том, в чем состоит это решение.
В этом разделе мы сначала приведем простой и наглядный пример интерактивного (т. е. в режиме двусторонней связи между Пи-карой и Вивалесом) доказательства с нулевым разглашением. Этот пример связан с раскрашиванием карты и не имеет отношения к теории чисел. Затем мы рассмотрим другой пример: как доказать, что вы нашли дискретный логарифм, никак не помогая проверяющему найти его значение. Далее мы обсудим понятие «скрытой передачи», с помощью которого можно строить неинтерактивные доказательства с нулевым разглашением. Наконец, мы используем скрытую передачу для доказательства знания разложения на простые множители с нулевым разглашением.
Раскраска карты. Рассмотрим первый пример. В настоящее время уже известно, что любую плоскую карту можно раскрасить четырьмя цветами. Некоторые карты можно раскрасить тремя цветами, а некоторые нет. Предположим, что Пикара имеет сложную карту, которую после долгих усилий она научилась раскрашивать только тремя цветами (г — красный, 6 — голубой, д — зеленый). Как ей убедить Вивалеса в том, что она умеет делать это, не давая ему намека, облегчающего ему поиск раскраски?
Сначала мы переформулируем задачу на языке теории графов.
Определение. Графом называется пара, состоящая из множества У, элементы которого называются «вершинами», и некоторого подмножества E множества всех (неупорядоченных) пар элементов множества V. Элементы E называются «ребрами». «Ребро» е = {u,v}, где и, V Є V, можно изображать линией, соединяющей вершины и я V.
Определение. Говорят, что граф можно раскрасить в цвета г, Ь,д, если существует такая функция /: V —> {г, Ь,д}, что {и, v} Є
§ 5. ПРОТОКОЛЫ С НУЛЕВЫМ РАЗГЛАШЕНИЕМ
131
E => f(u) ф f(v), т.е. никакое ребро не соединяет вершины одного и того же цвета.
Задача о трех красках состоит в определении того, можно ли данный граф раскрасить тремя цветами r,b,g.
Чтобы переформулировать задачу о раскрашивании карты в задачу о раскрашивании графа, следует просто взять в качестве V множество стран (изображая их теперь точками) и «соединять» две страны ребром в том и только том случае, если они имеют общую границу.
Задача о трех красках имеет два приятных свойства, делающих ее удобной для обсуждения многих вопросов: 1) она наглядна; 2) это NP-полная задача (по поводу этого понятия см. §4). Из свойства NP-полноты следует, что верификацию с нулевым разглашением любой NP-задачи можно свести к верификации с нулевым разглашением задачи о раскрашиваемости в три цвета.
Однако это не означает, что после построения верификации с нулевым разглашением некоторой NP-полной задачи F1 (скажем, раскрашиваемости в три цвета), ничего не стоит построить верификацию с нулевым разглашением для другой NP-полной задачи P2. Напротив, в процессе сведения задачи P2 к задаче F1 обычно значительно увеличивается размер входных данных. Поэтому более эффективной процедурой, скорее всего, будет прямая верификация с нулевым разглашением задачи P2, нежели сведение F2 к F1 с последующей верификацией с нулевым разглашением F1. Так, ниже мы приведем непосредственное доказательство с нулевым разглашением для возможности дискретного логарифмирования. Было бы в высшей степени неэффективно строить такое доказательство сведением задачи дискретного логарифмирования к задаче о трех красках для некоторого графа.
Доказательство с нулевым разглашением для задачи о трех красках. Предположим, что Пикара имеет некоторый граф. Мы будем представлять его вершины в виде маленьких цветных лампочек, помещенных внутри шариков, соединенных между собой трубками, изображающими ребра. Лампочки могут испускать красный, голубой или зеленый свет. У Пикары есть: 1) устройство А, позволяющее переключить любую вершину на любой из трех цветов, 2) устройство В, позволяющее нажатием одной кнопки совершить случайную перестановку на множестве цветов и переключение всех вершин в соответствии с этой перестановкой. Например, если устройство В выбрало транспозицию красного и голубого цветов, то все вершины, светившие голубым светом, переключаются на красный, все вершины, светившие красным, переключаются на голубой свет, а вершины, светившие зеленым светом, сохраняют его. Вивалес не управляет устрой-
132
ГЛ. IV. ОТКРЫТЫЙ КЛЮЧ
ством В и даже не знает, какая перестановка произошла.
Предположим далее, что поверхность шариков не позволяет увидеть свет лампочек снаружи. Однако, если проникнуть внутрь трубки, соединяющей две вершины, то будут видны огни находящихся в этих вершинах лампочек (и только они).
Пусть Пикара знает раскрашивание в три цвета и использует устройство А для установки соответствующих цветов в вершинах. Вот процедура, призванная убедить Вивалеса в том, что Пикара действительно знает такое раскрашивание.
1. Вивалес может заглянуть в любую трубку и увидеть цвета вершин на ее концах. Убедившись, что эти цвета различны, он получит определенное подтверждение того, что Пикара действительно знает правильную раскраску (напомним, что «правильной» является раскраска, при которой смежные вершины имеют разные цвета).
