однонаправленная хэш-функция:

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

(2)Пегги вручает решение n новых трудных проблем.

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

(4)Пегги берет n битов, полученных на этапе (3). По очереди для каждой n-ой трудной проблемы она берет n-ый бит и

(a)если бит равен 0, доказывает, что старая и новая проблемы изоморфны, либо

(b)если бит равен 1, раскрывает решение, врученное на этапе (2), и доказывает, что оно является реш е-нием данной новой проблемы.

(5)Пегги опубликовывает все решения, врученные на этапе (2), и все доказательства, полученные на этапе

(6)Виктор, Кэрол и все остальные заинтересованные лица проверяют, что этапы (1)-(5) выполнены правил ь-но.

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

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

В неинтерактивном протоколе должно быть гораздо больше итераций в последовательности запрос/ответ . Пегги, а не Виктор, отбирает трудные проблемы с помощью случайных чисел . Она может подбирать различные проблемы, следовательно, и различные векторы вручения, до тех пор , пока хэш-функция не выдаст что-то, нужное Пегги. В интерактивном протоколе 10 итераций - вероятность мошенничества Пегги составит 1 шанс из 2 10 (1 из 1024) - может быть достаточно. Однако, для неинтерактивных доказательств с нулевым знанием этого не хватит. Помните, что Мэллори всегда может выполнить на этапе (4) либо (a), либо (b). Он может, выполняя этапы (1)-(3), попытаться догадаться, что его попросят сделать, и посмотреть, правильно ли его предположение. Если нет, он попробует снова и снова. Сделать 1024 предположения на компьютере нетрудно. Для предотвращения такого вскрытия грубым взломом для неинтерактивных протоколов нужно 64 или даже 128 итераций.

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

Общие замечания

Блюм (Blum) доказал, что любая математическая теорема может быть преобразована в граф, такой, что д о-казательство теоремы будет эквивалентно доказательству существования гамильтонова цикла для этого графа . В общем виде то, что для любого NP-полного утверждения есть доказательство с нулевым знанием, использу ю-щее однонаправленные функции и, следовательно, хорошие алгоритмы шифрования, доказано в [620]. Любое математическое доказательство может быть преобразовано в доказательство с нулевым знанием . Используя эту методику, исследователь может доказать миру, что ему известно доказательство конкретной теоремы, не ра скрывая самого решения. Блюм мог опубликовать свои результаты, не раскрывая их .

Также существуют доказательства с минимальным раскрытием [590]. Для доказательства с минимальным раскрытием выполняются следующие свойства :

1. Пегги не может обмануть Виктора. Если Пегги не знает доказательства, ее шансы убедить Виктора в

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

2.Виктор не может обмануть Пегги. Он не получает ни малейшего намека на доказательство кроме того факта, что доказательство известно Пегги. В частности, Виктор не может продемонстрировать доказ а-тельство никому другому, не доказав все сам с самого начала.

У доказательств с нулевым знанием есть дополнительное условие :

3.Виктор не узнает от Пегги ничего такого, чего он не смог бы узнать и самостоятельно кроме того фа к-та, что доказательство известно Пегги .

Существует заметная математическая разница между доказательствами с минимальным раскрытием и док а-зательствами с нулевым знанием . Это различие находится вне рамок данной книги, но более искушенные чит а-тели могут проштудировать другую литературу. Понятия изложены в in [626, 619, 622]. Дальнейшая проработка этих идей, основанная на различных математических предположениях, выполнена в [240, 319, 239].

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

-Совершенное. Существует имитатор, который создает стенограммы, полностью соответствующие реал ь-ным стенограммам (примеры с гамильтоновым ци клом и изоморфизмом графов).

-Статистическое. Существует имитатор, который создает стенограммы, полностью соответствующие р е-альным стенограммам, кроме фиксированного числа исключений.

-Вычислительное. Существует имитатор, который создает стенограммы, неотличимые от реальных.

-Неиспользующее. Имитатора может и не быть, но мы можем доказать, что Виктор не узнает никакой информации из доказательства (параллельный пример)

Годы тяжелой работы, как теоретической, так и прикладной, присели к появлению доказательств с мин и-мальным раскрытием и нулевым знанием. Майк Берместер (Mike Burmester) и Иво Десмедт изобрели широковещательно интерактивное доказательство, где владелец секрета может широковещательно передавать большой группе контролеров интерактивное доказательство с нулевым знанием [280]. Криптографы доказали, что все, что может быть доказано с помощью интерактивного доказательства, может быть доказано и с помощью инт е-рактивного доказательства с нулевым знанием [753, 137].

Хорошей обзорной статьей по данной теме является [548]. Дополнительные математические подробности, варианты, протоколы и приложения ищите в [590, 619, 240, 319, 620, 113,241, 152, 8, 660, 238, 591, 617, 510, 592, 214, 104, 216, 832, 97, 939, 622, 482, 615, 618, 215, 476, 71]. Много чего было написано по этому вопросу.

5.2 Использование доказательства с нулевым знанием для идентификации

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

Использовать доказательства с нулевым знанием для доказательства идентичности было впервые предлож е-но Уриелем Файгом (Uriel Feige), Амосом Фиатом (Amos Fiat) и Ади Шамиром [566, 567]. Закрытый ключ Алисы становится функцией ее "идентичности" . Используя доказательство с нулевым знанием, она доказывает, что она знает свой закрытый ключ и, таким образом, свою идентичность . Соответствующие алгоритмы можно найти в разделе 23.11 .

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

Проблема гроссмейстера

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

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

На самом деле Каспаров играет с Карповым, а Алиса просто посредник, повторяющий ходы одного грос с-

мейстера на доске другого. Однако, если Карпов и Каспаров не знают о присутствии друг друга, каждый из них будет поражен игрой Алисы.

Этот способ мошенничества может быть использовать против доказательства личности с нулевым знанием [485, 120]. Когда Алиса доказывает свою личность Мэллори, Мэллори может одновременно доказать Бобу, что он-то и есть Алиса.

Обман, выполненный мафией

Обсуждая свой протокол идентификации с нулевым знанием, Ади Шамир сказал [1424]: "Я могу ходить в принадлежащий мафии магазин хоть миллион раз подряд, а они все еще не смогут выдать себя за меня ."

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

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

Обман, выполненный террористами

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

Когда Дэйв задает Кэрол вопросы в соответствии по протоколу с нулевым знанием, Кэрол передает их Ал и-се, которая и отвечает на вопросы. Кэрол повторяет эти ответы Дэйву. Carol recites these answers to Dave. По сути, Свою личность Дэйву доказывает Алиса, а Кэрол выступает в роли линии связи . Когда протокол завершается, Дэйв считает, что Кэрол - это Алиса, и разрешает ей въехать в страну . Спустя три дня Кэрол всплывает у правительственного здания вместе с микроавтобусом, набитом взрывчаткой .

Предлагаемые решения

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

Тотас Бот (Thomas Both) и Иво Десмедт предложили другое решение, использующее точные часы [148]. Если каждый этап протокола должен происходить в заданное время, у мошенников не останется времени для о б-мена информацией. В случае с проблемой гроссмейстера это соответствует предложению ограничить время о б-думывания хода одной минутой - у Алисы не останется времени бегать из комнаты в комнату . В истории с мафией у Боб и Кэрол не хватит времени передавать друг другу ответы и вопросы .

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

Существуют и другие способы злоупотребить доказательствами идентичности с нулевым знанием, также рассматриваемые в [485, 120]. В ряде реализаций проверка при регистрации человеком своего ключа не прои з-водится. Следовательно, у Алисы может быть несколько закрытых ключей и, таким образом, несколько личн остей. Это может здорово помочь ей, если она захочет мошенничать с налогами . Алиса также может совершить преступление и скрыться. В первых, она создает несколько личностей, одна из которых не используется . Затем, она использует эту личность для совершения преступления так, чтобы свидетель идентифицировал ее как эту личность. Затем, она немедленно прекращает пользоваться этой личностью . Свидетель знает личность преступника, но Алиса никогда больше не будет использовать эту личность - ее невозможно проследить .

Для защиты от этого нужны механизмы, обеспечивающие, чтобы у каждого человека была только одна ли ч-ность. В [120] авторами предлагается причудливая идея защищенных от воровства детей, которые не могут быть клонированы, и у которых есть уникальный номер, являющийся частью их генетического кода . Они также предложили присваивать каждому ребенку личность при рождении . (Действительно, родителям придется сде-