Кэрол невозможно убедить, потому что она не участвует в интерактивном процессе протокол. Для убеждения Кэрол и других заинтересованных лиц нам нужен неинтерактивный протокол .
Для неинтерактивных доказательств с нулевым знанием был придуман ряд протоколов [477, 198, 478, 197], которые не требуют непосредственного взаимодействия. Пегги может опубликовать их и, таким образом, док а-зать свое знание всем, у кого найдется время это проверить
Базовый протокол похож на параллельное доказательство с нулевым знанием, но место Виктора занимает
однонаправленная хэш-функция:
(1) Пегги использует свою информацию и п случайных чисел для преобразования трудной проблемы в п различных изоморфных проблем. Затем она с помощью своей информации и случайных чисел решает и новых трудных проблем.
(2) Пегги вручает решение п новых трудных проблем.
(3) Пегги использует все эти вручения в качестве входа для однонаправленной хэш-функции. (В конце концов эти вручения - не что иное, как строки битов.) Затем она сохраняет первые п битов полученного значения однонаправленной хэш-функции.
(4) Пегги берет п битов, полученных на этапе (3). По очереди для каждой и-ой трудной проблемы она берет й-ый бит и
(a) если бит равен 0, доказывает, что старая и новая проблемы изоморфны, либо
(b) если бит равен 1, раскрывает решение, врученное на этапе (2), и доказывает, что оно является реш е-нием данной новой проблемы.
(5) Пегги опубликовывает все решения, врученные на этапе (2), и все доказательства, полученные на этапе (4).
(6) Виктор, Кэрол и все остальные заинтересованные лица проверяют, что этапы (1)-(5) выполнены правил ь-но.
Это впечатляет: Пегги может опубликовать некоторые данные, которые не содержат никакой информации о ее секрете, но могут кого угодно убедить в существовании самого секрета. Этот протокол может быть использован проверка определена как вычисление однонаправленной хэш-функции первоначальных сообщений и подп и-сываемого сообщения.
Эта схема работает, потому что однонаправленная хэш-функция действует как беспристрастный генератор случайных битов. Чтобы мошенничать, Пегги нужно уметь предсказывать результат однонаправленной хэш-функции. (Помните, если решение трудной проблемы ей неизвестно, она может сделать на этапе (4) либо (а), либо (Ь), но не оба действия одновременно.) Если она каким-то образом узнает, выполнение какого действия потребует от нее однонаправленная хэш-функция, то она сможет смошенничать . Однако, Пегги не сможет заставить однонаправленную хэш-функцию выдать определенный бит или догадаться, какой бит будет получен. Однонаправленная хэш-функция по сути является заменителем Виктора в случайном выборе одного из двух доказательств на этапе (4).
В неинтерактивном протоколе должно быть гораздо больше итераций в последовательности запрос/ответ . Пегги, а не Виктор, отбирает трудные проблемы с помощью случайных чисел . Она может подбирать различные проблемы, следовательно, и различные векторы вручения, до тех пор , пока хэш-функция не выдаст что-то, нужное Пегги. В интерактивном протоколе 10 итераций - вероятность мошенничества Пегги составит 1 шанс из 2 10 (1 из 1024) - может быть достаточно. Однако, для неинтерактивных доказательств с нулевым знанием этого не хватит. Помните, что Мэллори всегда может выполнить на этапе (4) либо (а), либо (Ь). Он может, выполняя этапы (1)-(3), попытаться догадаться, что его попросят сделать, и посмотреть, правильно ли его предположение. Если нет, он попробует снова и снова. Сделать 1024 предположения на компьютере нетрудно. Для предотвращения такого вскрытия грубым взломом для неинтерактивных протоколов нужно 64 или даже 128 итераций.
Главная идея состоит в использовании однонаправленной хэш-функции - Пегги не может предсказать выход хэш-функции, потому что она не может предсказать ее вход. Вручения, используемые на входе, становятся известны только после решения новых проблем.