Где недостаток в методе Блюма-Фельдмана-Микали

Блум, Микали и Фельдман (BFM) выдвинули новую (криптографическую) модель, в которой все стороны (честные или состязательные) имеют доступ к некоторой строке. Предполагается, что строка выбирается в соответствии с некоторым распределением (обычно равномерным) доверенной стороной. Это называется ссылочной строкой , а модель точно названа моделью общей ссылочной строки (CSR).

Модель позволяет нам выполнять много интересных интерактивных протоколов неинтерактивно , заменяя запросы битами из ссылочной строки. В частности, доказательства с нулевым знанием для любого языка NP могут проводиться неинтерактивно, что порождает понятие неинтерактивного знания с нулевым знанием (NIZK).

NIZK имеет множество приложений, таких как предоставление метода для реализации криптосистем с открытым ключом, защищенных от (адаптивных) атак с выбранным шифротекстом .

BFM сначала доказал существование версии NIZK с одной теоремой для каждого языка NP ; то есть, дана ссылка строка и язык L ∈ N Р , можно доказать только одну теорему вида х ∈ L . Кроме того, длина теоремы ограничена в | ρ | , Если проверяющий попытается повторно использовать некоторые биты ρ в более поздних доказательствах, существует опасность утечки знаний (и доказательство больше не будет NIZK).$\rho$$L \in \bf{NP}$$x \in L$$|\rho|$$\rho$

Чтобы исправить это, BFM использовала версию с несколькими теоремами, основанную на единственной теореме NIZK. Для этого они использовали псевдослучайный генератор для расширения , а затем использовали расширенные биты. Есть и другие детали, но я не собираюсь вникать.$\rho$

Фейге, Лапидот и Шамир (в первой сноске на первой странице своей статьи) заявили:

Метод, предложенный в BFM для преодоления этой трудности, был признан ошибочным.

( Сложность относится к получению нескольких теоремных доказательств, а не одно теоремных.)

Где лежит недостаток BFM?

Я не читал подробности их некорректного протокола, но слышал об этом несколько раз. У меня сложилось впечатление, что их ошибка заключалась в том, как они использовали семена PRG. Их протокол помещает начальное число псевдослучайного генератора (PRG) в общедоступную общую строку ссылок, и они пытаются утверждать, что безопасность PRG заставляет некоторые статистические свойства вывода PRG сохранять даже с известным начальным числом. Хотя это возможно сделать разумным способом (схемы подписи Хоэнбергера и Уотерса здесь ум и здесь ), что-то пошло не так в их аргументации.