2
$\begingroup$

Is Schnorr's protocol for proving knowledge for a discrete logarithm, truly an interactive proof or is it an interactive argument? If we let P to be unbounded, after she generates the commitment $t$ and receives the challenge $c$ she can try all $r$ such that $h^r=t \cdot z^c$(where $h$ is the generator of the cyclic group and $z=h^x$)

In addition, how can we make any security guarantees if the prover is unbounded?

I know how to extract the witness from two transcripts. My intuition as to why this extraction argument is sufficient for proving soundness is something like this(correct me if I am wrong): If the prover can somehow cheat and produce two accepting transcripts, then she can extract $x$. This implies(by taking the contrapositive of that statement) that if she does not know $x$, then she cannot produce a transcript. Therefore, the protocol is sound.

However, in some sense we had to ignore the infinite computational power P has, while proving that statement. If she has infinite computational power, then she will always know the discrete log(because she can compute it). I guess my question is what is the purpose then for not bounding P?

$\endgroup$
  • $\begingroup$ Trying all $r$ is not the only way to use computing power. Having some $t z^c$, Prover could solve for discrete logarithm $r$. Or she could solve for $x$ from $z$ before the protocol. So how would you follow argument definition? $\endgroup$ – Vadym Fedyukovych Mar 10 '18 at 19:35
4
$\begingroup$

Schnorr's protocol is an interactive proof of knowledge. The 'attack' that you provide does not contradict this: if the powerful prover that you describes can indeed try all $r$ such that $h^r = t\cdot z^c$, then she can as well try all $x$ and check for $z=h^x$. Put otherwise, this prover does indeed know the discrete logarithm of $z$: in fact, any 'unbounded' prover knows the discrete log of $z$.

The proof that a prover that provides an accepting proof must know the discrete logarithm is done by using rewinding, and showing that a simulator could extract this discrete log from its interaction is quite straightforward (repeat the last two flows twice, write out the equations, cancel the randomness introduced in the first flow, and you get the witness); furthermore, if you write it, you'll observe that it does not rely on any computational assumption - if the verification succeeds with non negligible probability, extraction will succeed as well, with comparable probability. This holds independently of the computational power of the prover.

EDIT: to answer your follow up question, yes, you got the intuition right: if the prover can produce two accepting transcripts, she must know $x$, as $x$ can be extracted from these transcripts. Your issue seems to be that a computationally unbounded prover can always compute $x$, hence he always 'knows' $x$ - so, how is that interesting to consider also unbounded provers in the security analysis?

The answer lies in the formal guarantee given by a proof of knowledge. While the intuition is that it guarantees that the prover 'knows' the witness, the actual guarantee is the following: if the prover produces an accepting transcript, then a simulator can (using rewinding) extract the witness. This is of crucial importance in many cryptographic protocols where the proof of knowledge is part of a larger system: the simulator will often need to extract the witness from the proof, to use it when simulating other parts of the protocol. Now, in an argument, which is only secure against computationally bounded provers, an unbounded prover could well produce an accepting transcript from which the simulator cannot extract a witness - by breaking the computational assumption on which the knowledge soundness relies. Hence, even though this unbounded prover does indeed know a witness (she is unbounded, so she can obtain all witnesses via brute force), she does not necessarily allow the simulator to extract it from successful transcript, hence the analysis of ant larger system in which the simulator would need this witness would break down.

In Schnorr's protocol, however, as the soundness is unconditional, the simulator is guaranteed to always succeed in extracting the witness from the prover, even if she is unbounded.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ Thanks that makes sense. I do not have enough space here to ask a follow up question. Please see my edit. Thank you $\endgroup$ – Andreas G. Mar 10 '18 at 20:21
  • $\begingroup$ I edited my answer :) $\endgroup$ – Geoffroy Couteau Mar 10 '18 at 22:07

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.