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?

  • $\begingroup$ The Schnorr identification and signature protocol may be helpful? $\endgroup$ – DannyNiu Mar 13 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.

| improve this answer | |
  • $\begingroup$ Do you know also a solution that could be made non-intereractive? $\endgroup$ – Jan Moritz May 30 at 17:35
  • 1
    $\begingroup$ @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. $\endgroup$ – poncho May 30 at 17:44
  • $\begingroup$ I added a new question crypto.stackexchange.com/questions/81094/… Unfortunately the size of the proof does matter as well :/ $\endgroup$ – Jan Moritz May 30 at 17:49
  • $\begingroup$ 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. $\endgroup$ – Jan Moritz May 31 at 11:10

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

| improve this answer | |
  • 2
    $\begingroup$ 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... $\endgroup$ – poncho Apr 2 at 19:03

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.