15 votes
Accepted

Could Diffie-Hellman protocol serve as a zero-knowledge proof of knowledge of discrete logarithm?

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 ...
Geoffroy Couteau's user avatar
8 votes
Accepted

The definition and origin of Schnorr groups?

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 ...
Squeamish Ossifrage's user avatar
7 votes

Sigma protocol for AND-composition involving the same secret

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 ...
Berry Schoenmakers's user avatar
7 votes
Accepted

Zero-knowledge proofs vs. "Identification schemes"? (as in Katz--Lindell)

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, ...
Yehuda Lindell's user avatar
6 votes
Accepted

What's the main difference between the Schnorr identification scheme and its Smart-Card implementation?

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),...
fgrieu's user avatar
  • 140k
5 votes
Accepted

Is there any proof for ECDSA signature algorithm?

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 ...
ckamath's user avatar
  • 5,168
4 votes

Schnorr proof of group with unknown order (but the prover know the order)

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 ...
Yehuda Lindell's user avatar
4 votes
Accepted

In Schnorr identification protocol, what happens if the prover uses r+c+x or rx+c.. etc. rather than r+cx?

As you correctly note, the responses $rx+c$ and $rxc$ cannot be efficiently verified (without access to a Diffie-Hellman solver). The $r+c+x$ variant is a bad idea. Suppose as you say that Peggy has a ...
Daniel S's user avatar
  • 22.8k
3 votes

The definition and origin of Schnorr groups?

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 ...
fgrieu's user avatar
  • 140k
3 votes
Accepted

Schnorr identification protocol security proof

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 ...
fkraiem's user avatar
  • 8,112
3 votes
Accepted

What is difference between an identification scheme and a digital signature scheme?

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 ...
sha1's user avatar
  • 68
3 votes
Accepted

Schnorr protocol: how does malicious verifier win?

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 ...
DrLecter's user avatar
  • 12.5k
3 votes

Schnorr protocol: how does malicious verifier win?

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 ...
CurveEnthusiast's user avatar
3 votes
Accepted

What type of soundness/knowledge soundness does Schnorr's proof of knowledge of a DLOG have?

I answered the first part of the question here: Schnorr is a statistical proof of knowledge, with knowledge error $1/p$ (or $1/|C|$ if you pick the challenge from $C$). That is, one can always extract ...
Geoffroy Couteau's user avatar
2 votes
Accepted

Understanding the definition of Schnorrs identification protocol

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 ...
SEJPM's user avatar
  • 45.9k
2 votes
Accepted

Schnorr signature using discrete logarithm / problem with python implementation

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)}$.
Jérémy Métairie's user avatar
2 votes

How to make the interactive Schnorr identification protocol become non-interactive

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 ...
Lery's user avatar
  • 7,649
2 votes

Schnorr protocol: how does malicious verifier win?

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 ...
Vadym Fedyukovych's user avatar
2 votes
Accepted

Identification Schemes and Internet of Things

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 ...
Crowman's user avatar
  • 216
2 votes

Quantitative reduction of Schnorr's identification scheme to DLP

$ \newcommand{\sR}{\mathcal{R}} \newcommand{\sG}{\mathcal{G}} \newcommand{\sB}{\mathcal{B}} $ This is the best rigorous analysis I could come up with -- it uses the Splitting Lemma, but decided to ...
ckamath's user avatar
  • 5,168
2 votes
Accepted

Security proof of schnorr identification scheme

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-...
Crypto Learner's user avatar
2 votes

Discrete Logarithm Fiat-Shamir Parameters Selection

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 ...
Geoffroy Couteau's user avatar
2 votes
Accepted

batch Fiat-Shamir

One way to answer your question is to check if the following proof system is sound: Prover sends $R_1,\dots,R_n$ Verifier sends challenge $c$ Prover responds with $s_1,\dots,s_n$ Verifier checks for ...
lamontap's user avatar
  • 774
2 votes
Accepted

Impact of security of schnorr's identification verifier when reducing the challenge space

It all depends on what "reducing the challenge space" means. The most direct interpretation of the question is that we consider a normal 3-round Schnorr protocol, with the only modification ...
Marc Ilunga's user avatar
  • 3,163
1 vote

Case Scenarios where Identity Based identification (IBI) Scheme can be employed

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 ...
Daniel S's user avatar
  • 22.8k
1 vote

Proving equality of two Schnorr Signatures

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 ...
tylo's user avatar
  • 12.6k
1 vote

Orignal Schnorr Signature vs Discrete logarithmic Schnorr Signature

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 ...
fgrieu's user avatar
  • 140k
1 vote
Accepted

Difference between using Schnorr Protocol and just compare hash function to prove knowing something?

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 $...
fgrieu's user avatar
  • 140k
1 vote
Accepted

How many rounds is needed to implementing Schnorr Non-Interactive zero-knowledge protocol

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 ...
Kris's user avatar
  • 632
1 vote
Accepted

Questions regarding random values in Schnorr authentication

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 ...
Changyu Dong's user avatar
  • 4,168

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