#StackBounty: #rsa #number-theory Proving the knowlege of e-th root in an non-interactive way

Bounty: 50

Just like in this question: Protocol for proof of knowledge of $l$-th root

I want to prove that for $u^e = w$ I know $u$ without revealing it.
Three other requirements are:

  • e is small (65537)
  • The proof has to be non-interactive
  • The proof should be as efficient as possible (not several megabytes)


So the best solution I have come up so far is to use the Guillou-Quisquater protocol together with a Fiat-Shamir heuristic to make it non-interactive.
This would work the following way:

The prover

Step 1.

The prover generates 10 numbers $T1,T2 … T10$ where each number is calculated using the following formula and where $r$ is a secure random number:

$T = r^e$

Step 2.

calculate a hash $m’ = h(T1||T2 … T10||m)$ where $m$ is the message or challenge the prover wants to sign.

Note that if the hash contains 2 successive zero bytes or a zero byte followed by a byte of the value 1 of which the probability is low the prover has to go back to step 1 and generate new T numbers

Step 3.

The prover selects the 160 leading bits of the hash and splits them into 10 pairs of 16 bits numbers $d1,d2 .. d10$. Then for each of those 16 bits numbers calculates $t1,t2 … t10$ such that

$t = u^d r$

Note that in this case to calculate $t1$ the prover will use the random number $r$ that we used to calculate $T1$, for $t2$ the number $r$ used in $T2$ and so on.

Step 4.

The prover publishes the signed message $m$, the hash $m’$ and the numbers $t1,t2 … t10$

The verifier

Step 1.

The verifier starts by splitting the leading 160 bits of the $m’$ hash into the 16 bits number $d1,d2 .. d10$ then calculate the values $T1,T2 … T10$ from it:

$T = t^e w^{-d}$

Step 2.

Using the T values calculated in the previous step verify that $m’ = h(T1||T2 … T10||m)$ if this verification holds the proof is correct.

I do believe that doing this with 160 bits (proof with ten 16 bits numbers) is very secure, but what about doing it with 80, 96 or 128 bits?
Is there another way to improve this implementation or is there an error in it?

Get this bounty!!!

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.