# Probability of disavowing a signature in the Chaum-van Antwerpen Disavowal Protocol

Why in Chaum-van Antwerpen scheme, the probability that a cheating signer disavow a valid signature is $1/q$ ? From Handbook of Applied Cryptography at page 477:

Suppose that $s$ is indeed A’s signature for $m$, i.e., $s = m^a\ mod\ p$. Suppose that B follows Protocol 11.125 correctly, but that A does not. Then the probability that $c = c_1$ (and hence A succeeds in disavowing the signature) is only $1/q$.

In disavowal protocol, the signer must return two values $w$ and $w'$ to the verifier and these two values must satisfy:

$(w.\alpha^{-x_2})^{x'_1} = (w'.\alpha^{-x'_2})^{x_1} \ mod\ p$

I think the only way for the signer to compute such $w$ and $w'$ is as follows:

1. Guess two independent values $x_1,x'_1 \in \{1,2,\dotsc,q-1 \}$.
2. Compute $\alpha^{-x_2}$ from $((s^{-x_1}z)^{a^{-1}})^{-1}\ mod\ p$
3. Compute $\alpha^{-x'_2}$ from $((s^{-x'_1}z')^{a^{-1}})^{-1}\ mod\ p$
4. Select a random $w \in \{1, \dotsc,p-1\}$ and check wheter $w \ne m^{x_1}\alpha^{x_2}\ mod\ p$.
5. Calculate $w'$ which satisfies $(w.\alpha^{-x_2})^{x'_1} = (w'.\alpha^{-x'_2})^{x_1} \ mod\ p$.

But this way the probability of correct guess is $1/(q-1) \times 1/(q-1)=1/(q-1)^2$, as two values $x_1$ and $x'_1$ are independent.

Any idea ?

Chaum-van Antwerpen Disavowal Protocol:

(A: signer, B: verifier)

1. B obtains A's authentic public key $(p, \alpha, y)$.
2. B selects random secret integers $x_1,x_2 \in \{1, 2, \dotsc, q-1\}$, and computes $z=s^{x_1}y^{x_2}\ mod \ p$, and sends $z$ to A.
3. A computes $w=(z)^{a^{-1}} mod \ p$ ( where $aa^{-1}=1 \ mod\ p$ ) and sends $w$ to B.
4. If $w=m^{x_1}\alpha^{x_2}\ mod\ p$, B accepts the signature $s$ and the protocol halts.
5. B selects random secret integers $x'_1,x'_2 \in \{1, 2, \dotsc, q-1\}$, and computes $z'=s^{x'_1}y^{x'_2}\ mod\ p$, and sends $z'$ to A.
6. A computes $w'=(z')^{a^{-1}}\ mod\ p$ and sends $w'$ to B.

7. If $w'=m^{x'_1}\alpha^{x'_2}\ mod\ p$, B accepts the signature and the protocol halts.

8. B computes $c=(w\alpha^{-x_2})^{x'_1}\ mod\ p$ and $c'=(w'\alpha^{-x'_2})^{x_1}\ mod\ p$. If $c=c'$, then B concludes that $s$ is a forgery; otherwise, B concludes that the signature is valid and A is attempting to disavow the signature $s$.

Ref: Handbook of Applied Cryptography, page 477.