Притирка в эвристике Fiat-Shamir

Что мешает доказывающему перемалывать свои сообщения, чтобы подделать ложное доказательство?

Точно такой же вопрос мы могли бы задать и случайному оракулу! Что мешает доказывающему перемалывать свои сообщения, пока он не подделает поддельное доказательство? То, что вы предлагаете, может быть полностью сделано с помощью RO.

И ответ такой: сообщений должно быть очень мало $\альфа_1$ такой, что $\бета_1 = Н(\альфа_1)$ позволяет доказывающему иметь преимущество. В типичном $\Сигма$-протокол, например, когда утверждение не на языке (следовательно, доказывающий мошенничает), в среднем один $\альфа_1$ что позволяет доказывающему обманывать. (Упражнение: покажите, что это так для $\Сигма$-протокол для кортежей DDH, где слово $(Х,Y)$ и свидетель $х\в\mathbb{Z}_p$ такой, что $Х = г^х$ и $ Y = ч ^ х $). Следовательно, если есть $2^с$ возможные значения $\бета_1$ (это пространство испытаний), злонамеренный доказывающий должен будет вычислить $ О (2 ^ с) $ хэши для подделки поддельных доказательств. Теперь сделайте $с$ достаточно большой, и вы получаете вычислительную безопасность.

Обратите внимание, что атака измельчения по-прежнему является важным фактором: $\Сигма$-протоколы имеют безусловную безопасность, но как только вы скомпилируете их в ПЗУ с Fiat-Shamir, они имеют только вычислительный надежность. Это означает, что параметр безопасности для надежности (пространство запроса) должен быть скорректирован соответствующим образом: 40-битное пространство запроса подходит для $\Сигма$-протокол (поскольку он дает злоумышленнику $2^{-40}$ статистическая вероятность успешного взлома работоспособности, что на практике может быть приемлемым), но нарушается для Fiat-Shamir (поскольку для взлома составленного протокола требуется $2^{40}$ операции, которые тривиальны для выполнения). Как правило, мы будем использовать пространство задач о $2^{128}$ при использовании Фиат-Шамир.