Multi-user security for Schnorr-like signature schemes

Abstract

I denne oppgaven skal jeg først ta for meg et sikkerhetsbevis for Schnorr-signaturalgoritmen. Beviset inneholder flere steg der vi begynner med Schnorrs identifikasjonsprotokoll som er basert på vanskeligheten ved å løse det diskret logaritmeproblemet og ender opp med å vise at Schnorr-signaturalgoritmen som er et resultat av identifikasjonsprotokollen gjennom en Fiat-Shamir transformasjon er sikker i en setting med mange brukere. Beviset er veldig basert på det generiske beviset gitt i artikkelen Optimal Security Proofs for Signatures from Identification Schemes, men eksplisitt brukt på Schnorr-signaturalgoritmen med ekstra intuisjon. Etter dette tar jeg for meg Guillou-Quisquater-signaturalgoritmen og viser på tilsvarende vis som gjort i appendiks B i Optimal Security Proofs for Signatures from Identification Schemes for Schnorr-signaturalgoritmen, at dette også holder for Guillou-Quisquater-signaturalgoritmen. Til slutt forklarer jeg hvilke egenskaper til Guillou-Quisquater-signaturalgoritmen som er nødvendige betingelser for at beviset skal fungere.

In this thesis I will first consider a security proof of the Schnorr signature scheme from the single-user to the multi-user setting. The proof consists of several steps where we begin with the Schnorr identification scheme which is based on the hardness of the Discrete logarithm problem and conclude by showing that the Schnorr signature scheme derived through a Fiat-Shamir transformation is secure in the multi-user setting. This proof is heavily based on the generic security proof presented in the paper Optimal Security Proofs for Signatures from Identification Schemes, but explicitly applied to the Schnorr signature scheme with additional intuition. Next, I will look at the Guillou-Quisquater signature scheme and in a similar fashion as the slightly tighter proof of the Schnorr signature scheme presented in appendix B in Optimal Security Proofs for Signatures from Identification Schemes, show that this also holds for the Guillou-Quisquater signature scheme. Lastly, I will explain which scheme conditions are necessary for this proof to hold.