Caut o dovadă cantitativă, dar simplă a EUF-CMA securitatea unei scheme de semnătură obţinută prin transformarea Fiat-Shamir.
Reamintim, transformarea Fiat-Shamir pornește de la un protocol de identificare în 3 treceri cu mesaje $(I,r,s)$, Unde $I$ este angajamentul doveditorului, provocare $r$ este aleasă uniform la întâmplare în set $\Omega$ de către verificator, $s$ este dovada. Folosește un hash $H$ în $\Omega$.
Generarea perechii de chei $(\mathrm{pk},\mathrm{sk})$ în schema de semnătură este ca în protocolul de identificare. Pentru a semna mesajul $M$, dovatorul generează $I$ ca și în protocolul de identificare, calculează $r:=H(I,M)$, atunci $s$ ca în protocolul de identificare, apoi semnătura¹ $\sigma:=(I,s)$. Algoritmul de verificare calculează $r:=H(I,M)$ apoi aplica aceeasi procedura de verificare ca si protocolul de identificare, adica verificarea $\mathcal V(\mathrm{pk},r,s)=I$.
De cantitativ, adică presupunem că un adversar poate rupe schema de semnătură cu cel puțin probabilitate $\epsilon$ cu timp/efort $t$, $Q_S$ întrebări la oracolul semnăturii, $Q_H$ interogări la oracolul hash și obțineți o limită superioară a probabilității decât un adversar poate rupe schema de identificare cu ceva timp/efort.
Sunt bine cu o limită care se află într-un factor constant de la optim; care necesită orice proprietate plauzibilă pe schema de identificare cu 3 treceri, cum ar fi $I$ fiind uniform aleatoriu într-un set suficient de mare; $H$ fiind modelat ca un oracol aleatoriu; indiferent de algoritm care este timp polinom aleatoriu sau chiar determinist (inclusiv utilizarea unui PRG însămânțat cu $\mathrm{sk}$ și $M$ pentru banda aleatoare a algoritmului generator $I$, făcând astfel semnătura deterministă).
Știu că o referință standard este David Pointcheval și Jacques Stern Argumente de securitate pentru semnăturile digitale și semnăturile oarbe, în Journal of Criptology, 2000, dar aș vrea ceva mai simplu și mai concentrat.
¹ Semnătura poate fi, de asemenea $\sigma:=(r,s)$ sau $\sigma:=(I,r,s)$și există o reducere de securitate relativ simplă și strictă între cele trei.
