2
$\begingroup$

I basically use the method below, one difference is that after receiving the first proof the verifier asks the prover to create a proof for another challenge d and this several times without having the prover generate a new random value r. Is this safe? I was not able to find indications in the literature about it and r is never defined as a nonce but I am afraid this could leak the provers secret key A.

Guillou and Quisquater ([link][1]) present a zero-knowledge proof of an RSA signature. Basically, the scheme is as follows:

Public knowledge: RSA modulus $n$, public RSA exponent $v$, preimage $X$.

Secret knowledge for prover: $A$, such that $A^v = X \mod n$.

$$ \begin{matrix} \mathcal{P} & & \mathcal{V} \\ r \xleftarrow{\$} \mathbb{Z}_n^* \phantom{\mod n} & & \\ T \leftarrow r^v \mod n & & \\ & \xrightarrow{\quad{}T\quad{}} & \\ & & d \xleftarrow{\$} \{0,1,\ldots,v-1\} \\ & \xleftarrow{d} & \\ t \leftarrow A^dr \mod n & & \\ & \xrightarrow{\quad{}t\quad} & \\ & & t^v \stackrel{?}{=} X^{d}T \mod n \end{matrix} $$

In this diagram, $\leftarrow$ denotes assignment of a value to a variable and $\xleftarrow{\$}$ denotes uniformly random selection from a finite set.

[1]: http://dl.acm.org/citation.cfm?id=88372

$\endgroup$
  • 1
    $\begingroup$ The computation seems a bit tricky, but yes, knowing the prover answers to two different $d$ queries for the same $r$ allows extraction of $A$. The details are in the paper you cited and which is available as a PDF here (sections 2 and 3) and a bit too tricky for me to just whip out an answer. $\endgroup$ – SEJPM May 30 at 13:07
3
$\begingroup$

Is this safe?

No, it is not. Here is how it would be easy to recover $A$:

  • The prover generates $r$ and publishes $T$, and the verifier selects an arbitrary challenge $d$. The prover responds with $T = A^d \cdot r$

  • The prover generates the same $r$ and publishes the same $T$. The verifier selects the next $d' = d+1$ as his challenge, and the prover responds with $T' = A^{d'} \cdot r$

The verifier can then compute $T' \cdot T^{-1} = (A^{d+1} \cdot r) / (A^d \cdot r) = A$, thus recovering the secret.

I was not able to find indications in the literature about it and r is never defined as a nonce but I am afraid this could leak the provers secret key A.

Actually, it's not a nonce; calling something a nonce implies that the only requirement it has is that values never repeat, In this case, you can devise ways to exploit related $r$'s as well; for example, if it's a simple incrementing pattern, that is, $r' = r+1$, then the attacker just selects $d = d' = 1$. There might be nonrandom update patterns that are safe, but why risk it?

In general, using nonrandom challenges (either repeating or related) within a zero knowledge protocol does leak the secret.

| improve this answer | |
$\endgroup$

Your Answer

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

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