In the next few parts of this series, we look at various signature schemes and prove their security in the RO model. This part is dedicated to the analysis of Pointcheval and Stern Generic Signature Scheme of which the Schnorr scheme is an example. The generic scheme is built around a single pair. Later parts of this series will focus on ring signature schemes. Ring signatures embed the actual signer in a ring of other possible signers to hide her identity. We will discuss them in parts 3, 4, 5, 6, and 7.
2. Pointcheval and Stern generic signature scheme
For a given message , our generic scheme creates a signature where is a random element chosen from a pre-defined set, (i.e., RO output on query ), and is fully determined by and . By design, we require that the probability of selecting any particular be upper-bounded by for a given security parameter .
Schnorr’s signature scheme is an example that fits this generic model. To see why, recall that chooses a random commitment where is a pre-defined prime number. It then assigns where denotes a chosen generator of . Afterwards, is set to . Finally, is calculated as where denotes the signer’s private key. Note that can be any element of and so the probability that it takes on a specific value is equal to . By design, we choose the security parameter . This choice of guarantees that the aforementioned probability is upper-bounded by .