Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
2. Далее Пикара нажимает кнопку устройства В и переставляет цвета.
3. Вивалес снова заглядывает в одну из трубок.
4. Пикара и Вивалес поочередно повторяют шаги 2 и 3 до тех пор, пока Вивалес не проверит все трубки (или, по его желанию, пока он не проверит все трубки несколько раз — он может подозревать, что Пикара мошенничает при переключении лампочек в вершинах ранее проверенных ребер).
При недолгом размышлении становятся понятными следующие две вещи. 1) Если бы Пикара не знала правильного раскрашивания в три цвета, то она не смогла дурачить Вивалеса — рано или поздно с помощью шага 3 он обнаружил бы пару смежных вершин одного цвета. 2) Благодаря случайному переключению цветов Вивалес ничего не узнает о реальной раскраске, он лишь убедится в том, что она Пикаре удалась. Если он тоже хочет решить задачу о трех красках для данного графа, то после описанной процедуры эта задача останется для него столь же трудной, как и до того.
Чтобы доказать, что Вивалес ничего не узнал о раскрашивании, приведем следующее рассуждение. Пусть некоторое третье лицо, скажем, Клайд, не знает, как раскрасить граф тремя красками, но зато знает заранее, в какую трубку заглянет Вивалес. Тогда Клайд, зажигая на концах этого ребра лампочки разного цвета, может добиться в точности того же эффекта, что и Пикара. Таким образом, информация, которую Вивалес получает от Клайда, неотличима от той, которую ой, мог бы получить от Пикары. Но Клайд едва ли может сообщить ежу что-нибудь полезное о раскрашивании, так как сам ничего об этом не знает. Говорят, что Клайд «имитирует» действия Пикары. Этот прием имитации является стандартным способом до-
§ 5. ПРОТОКОЛЫ С НУЛЕВЫМ РАЗГЛАШЕНИЕМ
133
казательства того, что данный протокол является доказательством с нулевым разглашением.
Доказательство знания одного дискретного логарифма с нулевым разглашением. Как и в § 3, предположим, что G — конечная группа (относительно умножения) из N элементов, b — фиксированный элемент G и у — элемент G, для которого Пикара вычислила дискретный логарифм по основанию 6, т.е. решила уравнение Ьх = у относительно положительного целого х. Ей надо доказать Вивалесу, что она знает это решение, не давая никакой зацепки для определения этого решения. Сначала предположим, что Вивалесу известен порядок TV рассматриваемой группы. Вот последовательность шагов, которые они оба должны сделать.
1. Пикара вырабатывает случайное натуральное число е < TV и посылает Вивалесу b' = be.
2. Вивалес бросает монету. Если выподает «решка», то Пикара должна раскрыть значение е и Вивалес может проверить, что действительно b = Ье.
3. Если выпадает «орел», то Пикара должна сообщить наименьший положительный вычет числа х + е по модулю N, а Вивалес проверяет равенство yb' = Ьх+е.
4. Шаги 1-3 повторяются до тех пор, пока Вивалес не поверит, что Пикара знает значение х дискретного логарифма.
Заметим, что если Пикара в действительности не знает величины х, то она может давать правильный ответ не более чем при одном варианте выпадения монеты. Если при выполнении шага 1 она ожидает, что выпадет решка, то она может, не зная х, послать Вивалесу именно b' = be. Если она ожидает, что выпадет орел, то она должна послать Вивалесу b' = Ье/у (тогда на шаге 3 вместо х + е она сможет послать просто е), но если в этом случае выпадет решка, то она не сможет дать правильный ответ, так как не знает, в какую степень нужно возвести Ь, чтобы получить b .
Свойство отсутствия разглашения у этого протокола может быть обосновано с помощью приема имитации. А именно, пусть Клайд не знает дискретного логарифма у по основанию Ь, но зато знает заранее, как выпадет монета. Тогда он может имитировать шаги Пикары (посылая b' = Ье перед выпадением решки и b' = Ье/у перед выпадением орла). Получаемая в этом случае Вивалесом информация будет неотличима от информации, которую он мог бы получить от Пикары. При этом Клайд не может сообщить Вивалесу ничего полезного о значении дискретного логарифма, так как сам не знает его.
В упражнениях мы изучим ситуацию, когда Вивалес не знает
134
ГЛ. IV. ОТКРЫТЫЙ КЛЮЧ
величину N. Например, он может знать, что G = (Z/MZ)*, но не знать разложения числа M. (Напомним, что если M — произведение двух простых чисел, то знание разложения эквивалентно знанию N = ip(M), см. §1.3.) Тогда Пикара (или изображающий ее Клайд), которая пользуется величиной N на шаге 1, не должна давать Вивалесу никакой информации о N (иначе это не будет доказательством с нулевым разглашением). Это условие может показаться излишним, но любой вправе потребовать, чтобы передавалась лишь самая минимальная информация.
Скрытая передача. «Каналом скрытой передачи» информации от Пикары к Вивалесу называется система пересылки от Пикары к Вивалесу двух пакетов зашифрованной информации, удовлетворяющая следующим условиям.
1. Вивалес может дешифровать и прочитать только один пакет из двух.
2. Пикара не знает, который именно пакет он может дешифровать.
3. И Пикара, и Вивалес должны быть уверены, что условия 1 и 2 выполнены.
