4
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ The Schnorr identification and signature protocol may be helpful? $\endgroup$
    – DannyNiu
    Mar 13, 2020 at 10:45

2 Answers 2

Reset to default
3
$\begingroup$

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
$\endgroup$
4
  • $\begingroup$ Do you know also a solution that could be made non-intereractive? $\endgroup$
    – Jan Moritz
    May 30, 2020 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, 2020 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, 2020 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, 2020 at 11:10
1
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 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, 2020 at 19:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.