11

This is an interesting question. In fact, cryptographers have been using this exact protocol on many occasions, and there are two important reasons to prefer Schnorr over this protocol in most situations. The soundness of the protocol is not based on the Diffie-Hellman problem. This is probably the most important point to address. What does it mean for ...


8

What (and where) is the actual definition of a Schnorr group? Where have Schnorr groups first been introduced and who called them Schnorr groups? I don't know who first used the term—the earliest use I can dig up quickly is actually the Wikipedia article, initially drafted in November 2004 by Paul Crowley[1], who also used it a year earlier on sci....


7

I think I'm qualified to answer this question :-). The approach of going via identification schemes suffices for constructing secure signature schemes. Since this is the aim of this part of the book, it is much simpler than doing full blown zero knowledge. However, if you are interested in looking at sigma protocols and compilation to non-interactive zero ...


6

The standard paper used as reference for the Schnorr identification protocol and associated signature scheme is Claus-Peter Schnorr, Efficient Signature Generation by Smart Cards (alternative version), in Journal of Cryptology, 1991. Differences between this and the Schnorr identification protocol as in a modern textbook: The original exposition uses a ...


5

As pointed out by @SEJPM, you can read more about security proofs for DSA/ECDSA family on this thread. As for whether there exists an interactive protocol corresponding to DSA/ECDSA à la Schnorr identification/Schnorr signature, not that I am aware of. I would add that this is unlikely for two reasons: The (unfortunate) reason for coming up with DSA/ECDSA ...


4

Proving this statement for groups $G_1, G_2$ of different order is a bit tricky. If the groups are of the same order, one can simply use EQ-composition (see [4], which are the lecture notes corresponding to reference [3] above). For groups of different prime orders $p_1, p_2$, a simple $\Sigma$-protocol runs as follows. Let $n=p_1 p_2$. Prover sends ...


4

You are not wrong. This indeed does not work. The way out typically in these situations is to use a proof over the integers. There is quite a bit of work around zero knowledge over groups of unknown order. See Section 3.7 of this thesis by Geoffroy Couteau. Since he is active here, let's hope he weighs in.


3

Schnorr groups have been used by Schnorr in [Sc89a][Sc89b], [Sc90a][Sc90b], culminating with [Sc91]. These are the earliest detailed description of Schnorr groups of size relevant to cryptography that I could locate. The groups are then used in DSA of FIPS186 in [Ni94], without attribution to Schnorr. Drafts reportedly circulated starting August of 1991, but ...


3

Huh, I was just reading about this. Quoting [1]: Identification schemes: A can prove to B that he is A, but B cannot prove to someone Signature schemes: A can prove to B that he is A, but B cannot prove even to himself The distinction between identification and signature schemes is subtle, and manifests itself mainly when the proof is interactive and the ...


3

It is important to understand that the simulator is a non-interactive machine; it does not interact with the prover (or with anybody else). What it can do is mimic (or simulate) a real interaction between the prover and the verifier, by playing the roles of both parties and internally "sending messages to itself". But it is not required to mimic the protocol ...


3

I'll start by recalling what the (honest-verifier) zero-knowledge property actually means (informally). In case of honest-verifier zero-knowledge, the protocol is only zero-knowledge when interacting with an honest verifier. This is modeled in a way that the simulator has black-box access to the verifier but has full control over all input tapes of the ...


3

This all seems to be explained in the book (warning: large) you mention, all I mention here is taken from there. This is the last sentence before $\S18.3.2$: Enlarging challenge size not only improves performance (a positive result), in $\S18.3.2$ we will further see that this also has a negative consequence. Be careful, size matters! This last ...


3

Good that we have resolved the issue (the bug is to compute $g=h^{(p-1)/q} \bmod p$ instead of $g=h^{(p-1)/q} \bmod q$). When implementing such protocols you can take the following "rule of the thumb": When working with group elements of the multiplicative group $\mathbb{Z}_p^*$, i.e., performing group operations, then you always do your computations ...


2

No, this is not the case. We can't guarantee an honest prover is verified by a dishonest verifier (they could always lie and say "no, you failed"), but they could very well be authorized by the dishonest verifier (in addition to lying and saying "you passed" for everyone, they could act like the honest verifier if it's to their advantage). A dishonest ...


2

The difference is the amount of information you have about the structure of the numbers. Let $e\in_R\mathbb Z_q$. Then you know that the $e$ you have, is a random number from that set. You know no more and no less. Let $r=g^k$ for some $k\in_R\mathbb Z_q$. Then you know that the $r$ is a random number from the group and you know its discrete logarithm to a ...


2

Beware, notice the $s$ is computed modulo $(q-1)$ (due to Fermat's little theorem). You have to write $s = (k - (x * e)) \mod{ (q-1)}$.


2

The most common way to change an interactive Schnorr protocol into a non-interactive one is to rely on a random oracle. This is the so-called "Fiat-Shamir heuristic". Notice that a transcript in your case would look like $(r, e, y)$, where $e$ is the challenge the verifier sends to the prover. Now, you want to get rid of any interaction with the verifier to ...


2

There is zero knowledge and honest verifier zero knowledge; the difference is that honest verifier is less stringent by omitting verifier challenge from dataset that must be simulated in an indistinguishable way. Expected running time of the simulator must be polynomial in problem size. For this protocol running time is defined by challenge space ...


2

All that this part in the introduction is really saying is that identification is important to IoT. Much as we can say that, for electronic banking transactions, privacy is important (because otherwise people could read your financial transactions) but authentication is more important (because otherwise people could actually steal your money, which is worse),...


2

I believe this is the 'Rewinding Lemma' part of Schoor identification security proof, and very well explained in the Boneh and Shoup book "A Graduate Course in Applied Cryptography", pgs 727-728. An important aspect here is that we have to consider another adversary B, who emulates (grab a digital compiled version of A) and plays/interacts with A. (...


2

There seems to be a confusion here. As fgrieu stated correctly, Fiat-Shamir is a method to make a public-coin (honest-verifier) zero-knowledge proof non-interactive. You do not need to select any parameter for Fiat-Shamir, beyond the hash function: all other parameters are parameters of the interactive protocol which you are making non-interactive, or of the ...


1

Perhaps an extensible version of the Twitter blue checkmark scheme? A trusted central authority (Jack) sets up a parameterised system that allows signing keys to be produced whose verification keys match identifiers. A Twitter service user (Lil Nas) sets up an account with Jack. Jack carefully verifies that Lil Nas is whom they claim (or simply allows them ...


1

No, sending both parts of the proof together does not create any additional risk. Notice that at the end of the protocol, Victor knows the same set of values, regardless of whether it has been split into two rounds or not. So whatever he would be able to achieve in "one-round" version, he can still achieve after the second round of the two phase protocol.


1

I don't think that works with keeping the message private - unless you break the signature scheme by reusing the nonce. Your variables $c_1$ and $c_2$ are the results of the hash function. And those can not be the same by the definition of $r$ being a nonce. Moreover: the hash function does not retain any algebraic structure. By the definition of hash ...


1

The first publication using the Discrete Logarithm Problem (DLP) for asymmetric cryptography is in Diffie-Hellman key exchange. The original works in the multiplicative group $\Bbb Z_p^*$, or a typically large subgroup of that. The first use for signature is ElGamal signature. It uses the same kind of groups, and that makes its signature rather large. It ...


1

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 ...


1

Your first question: $r$ is taken from the group $Z_q$ ranging from 0 to $q-1$, and $q\equiv 0 \bmod q$, i.e. $q$ is the same as 0 in this group. Thus if you allow $q$ to be chosen, then $r$ is not uniform: you get 0 with a probability $2/(q+1)$ and all other elements in $Z_q$ with a probability $1/(q+1)$. Not really a big deal since the difference in ...


1

I do not know an exact citable source. However the rationale is roughly the following: The Decisional Diffie-Hellman Problem (DDHP) is not hard in $\mathbb{Z}_p^*$ since the Legendre symbol leaks the parity of the discrete log (DLOG) [1 section 5.1.2, 2]. You can use this fact to build an efficient algorithm to distinguish between Diffie-Hellman and non ...


1

I found the answer: Schnorr protocol is witness-hiding - proved in GGM model in https://www.shoup.net/papers/dlbounds1.pdf (as part of proof that Schnorr identification protocol is secure). At the same time, it's not possible to prove it in standard model based on discrete-log problem: http://www.cs.cornell.edu/~rafael/papers/schnorr.pdf


1

Let's change the formula to $C_1C_2=(g_1g_2)^{r}g_3^m$ and $C_2C_1^{-1}=(g_2g_1^{-1})^{r}g_3^m$. The prover just needs to prove that she knows how to open the two commitments as well as the random and the commited value are equal in two commitments, which is EQ form of [2] as you provided. Here is the protocol: The prover sends $a_1=(g_1g_2)^{u_1}g_3^{u_2}$ ...


Only top voted, non community-wiki answers of a minimum length are eligible