Я ищу количественное, но простое доказательство EUF-CMA безопасность схемы подписи, полученной преобразованием Фиата-Шамира.
Напомним, преобразование Фиата-Шамира начинается с протокола трехпроходной идентификации с сообщениями. $(я,р,с)$, куда $I$ это обязательство доказывающего, вызов $г$ выбирается равномерно случайным образом в множестве $\Омега$ по верификатору, $s$ является доказательством. Он использует хэш $Ч$ в $\Омега$.
Генерация пары ключей $(\mathrm{pk},\mathrm{sk})$ в схеме подписи как в протоколе идентификации. Подписать сообщение $ млн $, прувер генерирует $I$ как и в протоколе идентификации, вычисляет $r:=H(I,M)$, тогда $s$ как в протоколе опознания, то подпись¹ $\сигма:=(I,s)$. Алгоритм проверки вычисляет $r:=H(I,M)$ затем применяет ту же процедуру проверки, что и протокол идентификации, то есть проверку $\mathcal V(\mathrm{pk},r,s)=I$.
К количественный, я имею в виду, что мы предполагаем, что противник может взломать схему подписи с вероятностью не менее $\эпсилон$ со временем/усилиями $t$, $Q_S$ запросы к сигнатурному оракулу, $Q_H$ запросы к хеш-оракулу и получить некоторую верхнюю границу вероятности того, что злоумышленник сможет взломать схему идентификации, затратив некоторое время/усилия.
Меня устраивает граница, которая находится в пределах постоянного коэффициента от оптимального; требуя любого правдоподобного свойства схемы идентификации с тремя проходами, такого как $I$ быть равномерно случайным в некотором достаточно большом множестве; $Ч$ моделируется как случайный оракул; любой алгоритм, являющийся случайным полиномиальным временем или даже сделанный детерминированным (включая использование PRG, засеянного $\mathrm{sk}$ и $ млн $ для случайной ленты алгоритма генерации $I$, что делает подпись детерминированной).
Я знаю, что стандартная ссылка - это Дэвид Пойнтшеваль и Жак Стерн. Аргументы безопасности для цифровых подписей и слепых подписей, в Журнал криптологии, 2000 г., а хотелось бы что-то попроще и поконцентрированнее.
¹ Подпись также может быть $\сигма:=(r,s)$ или же $\сигма:=(I,r,s)$, и между этими тремя существует сравнительно простое и жесткое снижение безопасности.
