# Is it safe to reuse the same random session number r in the Guillou-Quisquarter protocol?

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.

• 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. – SEJPM May 30 at 13:07

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.