13
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 ...
- 18.9k
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 ...
- 47.6k
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 ...
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, ...
- 27.5k
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),...
- 137k
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 ...
- 5,113
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 ...
- 27.5k
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 ...
- 21.2k
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 ...
- 137k
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 ...
- 8,072
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 ...
- 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 ...
- 12.4k
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 ...
- 3,439
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 ...
- 18.9k
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 ...
- 45.6k
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)}$.
- 146
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 ...
- 7,579
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 ...
- 2,287
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 ...
- 226
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 ...
- 5,113
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-...
- 583
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 ...
- 18.9k
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 ...
- 632
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 ...
- 21.2k
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 ...
- 12.5k
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 ...
- 137k
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 $...
- 137k
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 ...
- 622
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 ...
- 4,138
1
vote
Accepted
Discrete logarithm problem particularly hard for Schnorr groups?
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 ...
Only top scored, non community-wiki answers of a minimum length are eligible