Abstrakt. Vi ser över säkerheten för Fiat-Shamir-signaturer i den icke programmerbara slumpmässiga orakelmodellen. Det välkända beviset från Pointcheval och Stern för sådana signatursystem (Journal of Cryptology, 2000) bygger på förmågan att omprogrammera det slumpmässiga oraklet, och det har varit okänt om denna egenskap är inneboende. Pailler och Vergnaud (Asiacrypt 2005) gav några första bevis för hårdheten genom att visa via meta-reduktionstekniker att algebraiska reduktioner inte kan lyckas med att minska nyckel-endast attacker mot oförfalskadhet till diskret-log antaganden. Vi använder också metareduktioner för att visa att Schnorr-signaturers säkerhet inte kan bevisas motsvara det diskreta logaritmproblemet utan att programmera det slumpmässiga oraklet. Vårt resultat håller också under en mer diskret logaritm antagande men gäller för en stor klass av minskningar, vi kallar singel-intance minskningar, subsumera de som används i tidigare bevis på säkerhet i (programmerbara) slumpmässiga oracle modellen. I motsats till algebraiska minskningar tillåter vår klass godtyckliga operationer, men kan bara åberopa en enda återställningsbar motståndare instans, vilket gör vår klass ojämförlig med algebraiska minskningar. Vårt huvudsakliga resultat handlar dock om metareduktioner och frågan om denna teknik kan användas för att ytterligare stärka separationerna ovan. Vårt svar är negativt. Vi presenterar, så vitt vi vet för första gången, begränsningar av metareduktion teknik i den meningen att hitta en meta-minskning för allmänna minskningar är mest sannolikt ogenomförbar. I själva verket bevisar vi att hitta en metareduktion mot en potentiell minskning är detsamma som att hitta en "meta-meta-reduktion" mot den starka existentiella oförfalskadheten i signatursystemet. Detta innebär att förekomsten av en metareduktion innebär att planen måste vara osäker (mot en något starkare attack) i första hand.
Fischlin och Fleischhacker REF utvidgade sitt resultat genom att visa att Schnorr-signaturers säkerhet inte kan baseras på det diskreta logaritmproblemet utan att programmera det slumpmässiga oraklet.
Limitations of the Meta-Reduction Technique: The Case of Schnorr Signatures
{'venue': 'IACR Cryptology ePrint Archive', 'journal': 'IACR Cryptology ePrint Archive', 'mag_field_of_study': ['Computer Science']}