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.

enter image description here

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?


1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.