# Proving the knowlege of e-th root in an non-interactive way

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)

EDIT

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?

• I'm guessing you are using modulo arithmetic and the modulus is large, right? – Nic May 30 '20 at 21:37
• @Nic Correct, this is actually a RSA signature – Jan Moritz May 30 '20 at 22:37
• You could Fiat-Shamir Transform the Guillou-Quisquater identification protocol which proves that you know $\chi$ in $X=\chi^e\bmod N$. – SEJPM May 31 '20 at 9:38
• @SEJPM this is what I was also thinking about, I edited the question and came up with a proposal of what you suggested. I would be happy if you can review it :) – Jan Moritz May 31 '20 at 11:40

## 1 Answer

Bad news is that what you ask for is impossible to achieve with the proposed Guillou-Quisquater (GQ) identification protocol. Unfortunately, $$\Sigma$$-protocols for group-homomorphisms are not efficient in groups of unknown order.

1) Efficiency Limitations of $$\Sigma$$-protocols in groups of unknown order

Informally speaking $$\Sigma$$-protocols in groups of unknown order for group-homomorphism $$\phi(\cdot)$$ have large knowledge error. This was shown by Bangerter et al. in case of generic-groups (see Theorem 6. in the linked paper). More specifically, in your specific scenario, the knowledge error of the GQ-protocol is $$1/e$$, where $$e$$ is your exponent (prime in your case). Hence, to achieve reasonable knowledge error, you need to repeat the protocol several times which would sacrifice the succinctness of your proof, given that supposedly your RSA group elements are already large (few thousand bits, I suppose).

For instance, let's take your setting: $$e=65537\approx2^{16}$$. Assuming you want to achieve $$128$$-bit security you need to repeat the GQ-protocol $$8$$ times. If you have $$2048$$-bit length for the modulus, then the proof size is $$2\cdot8\cdot2048$$ bit, which is $$4.096$$ kilobytes.

2) Circumventing the limitations by a trapdoor-free CRS

Efficiency limitations of $$\Sigma$$-protocols in groups of unknown order can be circumvented by applying a trapdoor-free CRS. In this case it is enough to repeat the $$\Sigma$$-protocol only once as it was shown by Boneh et al. Namely, the CRS would contain only a single group element whose DLOG should be not known to anyone. The downside of this approach is that it assumes a non-standard assumption, i.e. the Adaptive Root (AR) assumption. As of today we know quite little about AR. For example, it is not known yet whether AR is equivalent to Factoring in the generic ring model or not. However, we do know that AR holds in the generic group model, although this is not a decisive result as the generic group model is quite a restricted computational model.

3) Making $$\Sigma$$-protocols non-interactive

There are standard ways to implement the FS-heuristic. However, there are some pitfalls you need to have in mind. In the weak-FS (wFS) the challenge is computed as the hash of the commitment (first message of the prover). In the strong-FS (sFS) the challenge is obtained by hashing both the statement and the commitment. It was shown by Bernhard et al. that a protocol implemented with the wFS becomes insecure if a malicious prover can adaptively choose her statements she wants to prove. So to be on the safe side always implement FS with the strong variant.

TL,DR: either you have an inefficient protocol or you need to assume a non-standard RSA assumption, called the Adaptive Root assumption.

• So using 8 iterations of the GQ-protocol is the most efficient way you know of? – Jan Moritz Jun 7 '20 at 12:06
• The most efficient way is to use the technique by Boneh et al. That's just a single iteration of a $\Sigma$-protocol but it assumes a novel RSA assumption. – István András Seres Jun 7 '20 at 12:17