1
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.