0
$\begingroup$

I'm reading Proof Systems for General Statements about Discrete Logarithms, and I think I'll have a better understanding of the process if I can understand where the terms come from. They give a basic example which I'll just post a snapshot of below:

enter image description here

Can someone explain the logic behind the naming of these terms?

$\endgroup$

1 Answer 1

2
$\begingroup$

This is because:

  1. For the commitment $t$, it comes first and uses the difficulty of the discrete logarithm problem to protect the value $v$. Once you've published the value $t=g^v \bmod q$, if someones knows the value $v$, then they can easily verify that the value $t$ corresponds to the value $g^v \bmod q$, but on the other hand it is really difficult to find the value $v$ knowing only the value $t$. Hence, you commit to the knowledge of the value $v$ by giving out the value $t$.
  2. For the challenge $c$, you can see this value as being a "challenge": anybody able to give you a value $r$ such that $g^ry^c=g^v=t \bmod q$ must be knowing the value $x$, otherwise they wouldn't have been able to compute $r$ such that the $y^c=g^{xc}$ cancels out with the $g^r$ value. So you challenge them to provide you with a correct $r$ value.
  3. And for the response $r$, it is an answer to the question of finding a value $r$ such that $g^ry^c=g^v$. If you know $x$ and $v$ then you can compute the value $r$ in such a way that the challenge would not be hard, but if you do not know those values, your chances to find a correct value $r$ are negligible. So you're responding to the challenge using that value $r$.

This is possible in the end because $g^ry^c=g^rg^{xc}=g^{v-xc}g^{xc}=g^v=t$ by definition of $y$ and $r$.

I'm speaking $\bmod q$ for all of it to hold, obviously.

$\endgroup$

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.