Protocol for proof of knowledge of $l$-th root

Assume we have Group G in which the adaptive root assumption holds. This assumption states that if we choose an element $$w$$ and after that, if we receive a prime value $$l$$ it is hard to find the $$u$$ such that: $$u^l = w$$

Now suppose I want to prove that I know a $$l\text{-}th$$ root of an element $$w$$ without revealing it. (I don't want to reveal $$u$$). Is there any protocol for this?

• The Schnorr identification and signature protocol may be helpful? Mar 13 '20 at 10:45

The immediately obvious solution would be this simple cut-and-choose protocol:

• Prover: selects a random value $$v$$ and sends the value $$y = v^\ell$$

• Verifier: selects and sends a random bit $$b$$

• Prover: if $$b=0$$, sends the value $$t_0=v$$. If $$b=1$$, sends the value $$t_1=vu$$

• Verifier: if $$b=0$$, then verify that $$t_0^\ell = y$$. If $$b=1$$, then verify that $$t_1^\ell = y w$$

The standard zero knowledge logic works - if the prover knows a $$y$$ value for which he knows both correct responses $$t_0$$ and $$t_1$$, then (assuming that inverses are also easy to compute) he can recover the value $$u$$ (hence, if he succeeds with this protocol a number of times, then the probability of success without him knowing $$u$$ is minimal). And, only one of the answers does not give any information to the verifier.

• Do you know also a solution that could be made non-intereractive? May 30 '20 at 17:35
• @JanMoritz: if you don't mind long non-interactive proof, the standard way to convert a cut-and-choose protocol into noninteractive works (the prover publishes a long series ($n$ values) of $y$ values $y_1, y_2, …, y_n$; he computes the values $b_1, b_2, …, b_n$ based on the hash of all those $y$ values, and then the series of values $t_{i, b_i}$ values computed as above. The verifier then hashes the $y$ values to recreate the $b_i$ values, and then individually verified the $t$ values. This is chatty (the proof might be circa a megabyte), but it works. May 30 '20 at 17:44
• I added a new question crypto.stackexchange.com/questions/81094/… Unfortunately the size of the proof does matter as well :/ May 30 '20 at 17:49
• I edited the question crypto.stackexchange.com/questions/81094/… so that it now contains a proposal on how to do it with the GQ protocol. May 31 '20 at 11:10

"Deep coins" protocol by Guillou and Quisquater: https://link.springer.com/content/pdf/10.1007/3-540-45961-8_11.pdf

• With this protocol, a cheater has a probability $1/\ell$ of being able to fool a single pass (by guessing $d$ beforehand); with the cut-and-choose, they have a $0.5$ probability. For large $\ell$, this is much better; for $\ell = 3$, well, it's a lot closer... Apr 2 '20 at 19:03