On the Exact Security of Schnorr-Type Signatures in the Random Oracle Model
The Schnorr signature scheme [Sch89,Sch91], derived from the Schnorr identification scheme (an honest-verifier zero-knowledge proof of knowledge of a discrete logarithm) through the Fiat-Shamir transform, is one of the earliest discrete log-based signature schemes proposed in the literature. Its simplicity and efficiency (short signature length and the possibility of pre-computing exponentiations for very quick on-line signature generation) has attracted considerable attention. Its security has been analyzed in the Random Oracle Model (ROM) under the Discrete Logarithm (DL) assumption by Pointcheval and Stern. The main idea of the proof is to have the forger output two distinct forgeries corresponding to the same random oracle query, but for two distinct answers of the random oracle.