0
$\begingroup$

I am studying Schnorr Protocol and I just come up a case.

For example I am a Prover and have a secret $x$. By using Schnorr Protocol, I create $h=g^x \bmod p$ and save $h$ to a public place.

When a Verifier need to prove to Prover,

  1. prover sends a commitment to verifier $c = g^r \bmod p$ where $r$ is a random value
  2. verifier sends a challenge to prover $t$ is a random value
  3. prover sends a response to verifier $s = r + t\,x$
  4. verifier accepts iff $g^s \bmod p= c\,h^t\bmod p$

What is the difference if I store a hashed value for example $h = \operatorname{sha512}(x)$ to a public place, and if prover want to prove he know secret $x$, he just need to send $h'$ to verifier and verifier compare if $h = h'$ stand.

I know that a dishonest prover can send the hash to verifier directly to fool the verifier. Apart from this, is there any difference? Seem using hash can still prove the prover know secret $x$.

$\endgroup$
  • $\begingroup$ Thanks for you reply. So do you mean in attacker can easily find $x$ in step 3? $\endgroup$ – Jeff Lee Mar 25 at 11:44
  • $\begingroup$ I mean that with the question's currently incorrect characterization of what the prover does as step 3, an adversary impersonating the verifier can find $x$, which goes against the goal and achievement of the proper Schnorr protocol. I'm encouraging you to understand why, and accordingly correct step 3. Hint: the order of $g$ comes into play. $\endgroup$ – fgrieu Mar 25 at 11:48
  • $\begingroup$ Sorry, I am very new to cryptography. If r and t is selected randomly within the order of $g$, $x$ should be secure? $\endgroup$ – Jeff Lee Mar 25 at 12:01
  • $\begingroup$ Crypto is about adversaries doing everything they can to foil protocols. An adversary can act as the verifier with respect to the prover, choose $t$, and get the corresponding $s$. Assume that the adversary chooses the largest $t$ that the prover will accept at step 2 (which is also the largest $r$ that the prover will generate at step 1, and the largest possible $x$), and the prover computes and reveals the corresponding $s = r + t\,x$ as the current step 3 says. Do you see how that's extremely revealing about $x$? Try is with $x$, $t$ and $s$ limited to a fixed number of decimal digits. $\endgroup$ – fgrieu Mar 25 at 12:11
  • $\begingroup$ Ohhhh I see, so $s=(s-r)/t$ with know s and large t, effect of r is ignorable, so x can be reveal. So do you mean using hash approach is much more safer?? $\endgroup$ – Jeff Lee Mar 25 at 12:21
0
$\begingroup$

The question does not correctly describe the Schnorr protocol. Here it is (with restriction to a multiplicative subgroup of $\Bbb Z_p^*$, because that's in the question).

It is chosen a large prime $q$ (e.g. $>\approx 2^{512}$) and a larger prime $p$ (e.g. $>\approx 2^{8192}$) with $p=2\,a\,q+1$ for some integer $a\ge1$ (with $p$ not of a special form facilitating SNFS), and an integer $g$ of order $q$, that is with $g^q\bmod p=1$ and $g\bmod p\ne1$ (one such $g$ is $4^a\bmod p$). Parameters $p$, $q$, $g$ are public.

A random secret $x\in[0,q)$ is known to a Prover, who publishes $h=g^x\bmod p$. The above choice of parameters $p$, $q$, $g$ is such that the Discrete Logarithm Problem of finding $x$ given $h$ is believed hard.

The protocol's goal is that a verifier gets rightly convinced that a party knowing $x$ with $h=g^x\bmod p$ participates in the protocol, without revealing $x$ to the prover or to adversaries, including active (in particular, adversaries are able to impersonate the prover w.r.t. the verifier, and vice versa). Towards this:

  1. Prover draws a random value $r\in[0,q)$ and sends commitment $c=g^r\bmod p$
  2. Verifier draws a random value $t\in[0,q)$ and sends that challenge to prover.
  3. Prover computes and sends response $s=r+t\,x\bmod q$
  4. Verifier is content that prover knows $x$ iff $g^s\bmod p=c\,h^t\bmod p$

That equality normally holds because $s=r+t\,x\bmod q$ implies that $\exists k,\ s+k\,q=r+t\,x$ therefore $g^s\equiv g^{r+t\,x-k\,q}\equiv g^r\,g^{t\,x}\,g^{-k\,q}\equiv c\,(g^x)^t\,(g^q)^{-k}\equiv c\,h^t\,1^{-k}\equiv c\,h^t\pmod p$.

It can be shown that breaking this protocol is equivalent to solving the DLP.


What is the difference if I store a hashed value for example $h=\operatorname{SHA-512}(x)$ to a public place, and if prover wants to prove he knows secret $x$, he just need to send $h'$ to verifier and verifier compare if $h=h'$ stands.

The proposed protocol fails to prove to the verifier that another party knowing $x$ participates in the protocol. Argument: since $h$ is in a public place, an adversary not knowing $x$ can get $h$, send that as $h'$ like the prover knowing $x$ is supposed to do, and thus pass the verifier's test.

If prover and verifier both know $x$, a solution is possible using $\operatorname{SHA-512}$ in a challenge-response protocol: verifier draws and sends random $t$, prover computes and sends $s=\operatorname{SHA-512}(t\mathbin\|x)$, verifier checks $s=\operatorname{SHA-512}(t\mathbin\|x)$.

The advantage of Schnorr's protocol is to achieve the same goal without requiring the verifier to know $x$. In particular, in the MAC-based protocol, the verifier must keep $x$ secret, which is hard even for an honest verifier, and is not necessary with Schnorr's protocol.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ The protocol using MACs is generally (i.e. for an arbitrary MAC) not secure, because $x$ is not necessarily uniform. $\endgroup$ – Maeher Mar 26 at 7:45
  • $\begingroup$ That's not the issue though. Schnorr is a PoK regardless of the distribution of $x$. (This guarantee is naturally only really meaningful if the distribution has high min-entropy, but that's besides the point.) Your proposed proposed protocol is (a) not a PoK: what's even the language here? How would extraction work? (b) not generally "sound" since I can give a secure MAC scheme and a high min-entropy distribution for $x$ such that a prover can succeed without knowing $x$. $\endgroup$ – Maeher Mar 26 at 9:30
  • $\begingroup$ @Maeher: If your objection still stands with the revised answer, I fail to get it. Isn't ability to compute $\operatorname{SHA-512}(t\mathbin\|x)$ for random challenge $t$ a proof of (having access to some resource with) knowledge of $x$, as good as what is demonstrated by applying Schnorr's protocol, leaving aside the "detail" that the verifier needs to know $x$ but keep it secret? Note: I can understand that ability to compute $\text{HMAC-SHA-512}(x,t)$ for random challenge $t$ does not quite apply, since for $x$ larger than 1024 bit, only knowledge of $\text{SHA-512}(x)$ is demonstrated. $\endgroup$ – fgrieu Mar 26 at 10:39
  • $\begingroup$ An interactive proof is defined for an NP relation. What is that relation? Proof of knowledge is defined as an interactive proof for which there exists an extractor that can extract the witness from interaction with the prover. How do you extract $x$ (which should be the witness, though again I fail to see for which relation) from interaction with the prover? $\endgroup$ – Maeher Mar 26 at 10:43
  • $\begingroup$ (Technically you can have interactive proofs for all of PSPACE, but the concept of a proof of knowledge only makes sense in the presence of a witness relation) $\endgroup$ – Maeher Mar 26 at 11: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.