# Proving an identification-scheme based on a digital signature is secure

I am trying to prove to myself that an identification scheme derived from a digital signature in a challenge/response manner is secure, based on the security of the digital signature scheme. I've found an informal proof in these lecture notes, but I'm struggling to formalize it with a reduction.

Let $$\Sigma = (GEN, SIGN, VERIFY)$$ be a digital signature scheme, and $$\mathcal{ID}^{\Sigma} = (IDGEN, P, V)$$ be an identification scheme derived from the digital signature, in particular:

• $$IDGEN = GEN$$
• The prover $$P$$ takes a keypair $$(sk, pk)$$, receives a challenge $$r$$ from the verifier $$V$$, and returns a signature $$\sigma = SIGN(sk, r)$$ over the message
• The verifier $$V$$ takes a public key, generates a random challenge $$r \in \{0,1\}^m$$, sends it to the prover, receives a signatures $$\sigma$$, and accepts the proof iff the signature verifies $$VERIFY(pk, r, \sigma)$$

It seems to me that the security of the identification scheme should reduce straightforwardly to the security of the underlying digital signature. So I attempt the following reduction.

Let $$\mathcal{A}$$ be an adversary that succeeds in an active impersonation attack against the identification scheme with $$Adv(\mathcal{A})$$. That is, $$\mathcal{A}$$ receives a public key $$pk$$ drawn from $$(sk, pk) \xleftarrow{} IDGEN()$$, gets to interact with a polynomial number of prover oracles instantiated with the private key $$P_{(sk,pk)}(\cdot)$$, and after losing oracle access, must convince an honest verifier $$V_{pk}(\cdot)$$ to accept. $$Adv(\mathcal{A}) = \Pr[VERIFY(pk,r,\sigma)]$$

We now construct an adversary $$\beta$$ that succeeds in breaking the security of the underlying digital signature. $$\beta$$ accepts a public key $$pk$$ from the digital signature challenger, and feeds it to $$\mathcal{A}$$. $$\beta$$ then simulates the prover oracles to $$\mathcal{A}$$ by receiving $$q$$ challenges $$r_i$$ from $$\mathcal{A}$$, asking the digital signature challenger to sign these challenges, receiving $$\sigma_i = SIGN(sk, r_i)$$, and sending back the signature to $$\mathcal{A}$$. After $$\mathcal{A}$$ is done interacting with the prover oracles, $$\beta$$ acts as the honest verifier to $$\mathcal{A}$$ by picking a random $$r$$, receiving a candidate signature $$\sigma$$, and verifying the signature $$VERIFY(pk, r, \sigma)$$. $$\beta$$ will also forward the signature $$\sigma$$ to the digital signature challenger. Note that $$\beta$$ will win the digital signature game if $$\mathcal{A}$$ succeeds in their impersonation attack, and the signature is over a challenge $$r$$ that $$\beta$$ has not asked to be signed earlier. That is, $$Adv(\beta) = \Pr[VERIFY(pk,r,\sigma) \land (r,\sigma) \notin \{(r_i, \sigma_i)\}]$$.

Now we need to relate the success of the digital signature adversary $$\beta$$ to the success of the id scheme adversary $$\mathcal{A}$$. So far I have,

• $$Adv(\beta) = \Pr[VERIFY(pk,r,\sigma) \land (r,\sigma) \notin \{(r_i, \sigma_i)\}]$$
• $$\Pr[VERIFY(pk,r,\sigma)] = Adv(\mathcal{A})$$
• $$\Pr[(r,\sigma) \notin \{r_i, \sigma_i\}] = 1 - \frac{q}{2^m}$$

It's not clear to me where to go from here. Ideally, I'd like some expression or inequality relating $$Adv(\mathcal{A}), Adv(\beta)$$ such that if the former is large, so is the latter.

We can use conditional probability to get something like $$\Pr[VERIFY(pk,r,\sigma) \land (r,\sigma) \notin \{(r_i, \sigma_i)\}] = \Pr[VERIFY(pk,r,\sigma) \vert (r,\sigma) \notin \{(r_i, \sigma_i)\}] \times \Pr[(r,\sigma) \notin \{(r_i, \sigma_i)\}]$$, but nailing down the first part of that product is hard. We could also use boole's inequality (union bound for intersections), but that gets us a rather trivial $$\Pr[VERIFY(pk,r,\sigma) \land (r,\sigma) \notin \{(r_i, \sigma_i)\}] \geq \Pr[VERIFY(pk,r,\sigma)] + \Pr[(r,\sigma) \notin \{(r_i, \sigma_i)\}] - 1$$

Been racking my brain at this for a while... it seems like the security should trivially follow but the math ain't mathing. Any thoughts?

Let event $$A$$ denote $$VERIFY(pk,r,\sigma)$$ and event $$B$$ denote $$(r,\sigma) \notin \{r_i, \sigma_i\}$$. Then, \begin{align}Adv(\mathcal{A})=\Pr[A]&=\Pr[A\wedge B] + \Pr[A\wedge \bar B] \\&\leq\Pr[A\wedge B]+ \frac{q}{2^m}\\&=Adv(\beta) + \frac{q}{2^m} \end{align} We have $$Adv(\beta)\geq Adv(\mathcal{A})- \frac{q}{2^m}$$ which is good enough for the reduction if $$q$$ is polynomial in $$m$$. The law of total probability is what I used on the first line.