Correctness Archives

Download pdf here: Pointcheval and Stern Generic Signature

1. Introduction

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 $(sk,pk)$ 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 $m$ , our generic scheme creates a signature $\sigma(m) \equiv (r,h,\alpha)$ where $r$ is a random element chosen from a pre-defined set, $h = \mathcal{H}(m,r)$ (i.e., RO output on query $(m,r)$ ), and $\alpha$ is fully determined by $m, r,$ and $h$ . By design, we require that the probability of selecting any particular $r$ be upper-bounded by $\frac{1}{2^{k-1}}$ for a given security parameter $k$ .

Schnorr’s signature scheme is an example that fits this generic model. To see why, recall that $\Sigma_{Schnorr}$ chooses a random commitment $k \in \mathbb{Z}^{*}_{q}$ where $q$ is a pre-defined prime number. It then assigns $r \equiv g^{k}$ where $g$ denotes a chosen generator of $\mathbb{Z}^{*}_{q}$ . Afterwards, $h$ is set to $\mathcal{H}(m,r)$ . Finally, $\alpha$ is calculated as $k-hx$ where $x$ denotes the signer’s private key. Note that $r$ can be any element of $\mathbb{Z}^{*}_{q}$ and so the probability that it takes on a specific value is equal to $\frac{1}{q-1}$ . By design, we choose the security parameter $k \leq log_{2}(q)$ . This choice of $k$ guarantees that the aforementioned probability is upper-bounded by $\frac{1}{2^{k}-1} \leq \frac{1}{2^{k-1}}$ .