Questions tagged [sigma-protocol]
Sigma protocols are a special form of zero-knowledge proof. They can be turned into non-interactive proofs using the Fiat-Shamir heuristic.
31
questions
0
votes
1
answer
60
views
Special Soundness $\Sigma$-Protocols
About the characterizations of Special Soundness, from Staking Sigmas we have that:
''A $\Sigma$-protocol $\Pi=(A,Z,\phi)$ is said to have ${\it special\ soundness}$ if there exists a PPT extractor $\...
- 187
0
votes
0
answers
40
views
Verifying a random subset of a parallel repitition of sigma protocols
Suppose a prover computes a non-interactive proof which is composed of $k$ parallel repetitions of a sigma protocol with binary challenges (and knowledge error $\frac{1}{2}$), composed in parallel and ...
- 413
2
votes
1
answer
81
views
Fiat-Shamir with interactions
Suppose we have a standard $\Sigma$-protocol for proving the knowledge of a witness $x$ for the statement $y$. It has an honest-verifier ZK and special soundness. Now we do an unusual modification to ...
- 548
2
votes
2
answers
294
views
How to calculate soundness error of a sigma protocol?
How do I calculate the soundness error of a sigma protocol, such as Schnorr's interactive protocol for knowledge of a discrete logarithm?
0
votes
0
answers
188
views
Difference between sigma protocol, Schnorr protocol, Pedersen commitment
Could you explain the difference between sigma protocol, Schorr protocol with examples. What is the advantage of using commit-and-prove zero knowledge proof over general zero knowledge proof?
- 179
1
vote
1
answer
61
views
Input Delayed Sigma-Protocol
In a Sigma-protocol, the steps are (1) commitment, (2) challenge, and (3) response. In general, the prover has a statement and witness that they can use to compute the commitment step. But in some ...
- 395
2
votes
1
answer
192
views
Extending the OR-proof to more than two statements
I have been reading about the sigma protocols, specially the OR-Proof.
Many examples just take into account two statements and provide a way to say that one of the statements is valid, but not which ...
- 21
3
votes
1
answer
271
views
Intuition Behind Commitment-Challenge-Response a.k.a. Sigma Protocols
In How To Prove Yourself: Practical Solutions to Identification and Signature Problems, Fiat and Shamir introduce a zero-knowledge identification scheme where
The prover sends a commitment to the ...
- 229
0
votes
3
answers
251
views
The challenge c in Sigma protocol (using Fiat Shamir)
As is known to all, the following picture depicts a sigma protocol, and to eliminate the interactivity, Prover can generate c by hashing (t, y) using Fiat Shamir transform. My question is:
1). Can c ...
0
votes
1
answer
80
views
What is the adversary advantage for soundness of a sigma protocol?
Does a sigma protocol have an adversary advantage of zero for soundness? Or is this affected by the probability distribution of the indistinguishability of the simulator? Will in that case using the ...
- 243
4
votes
2
answers
484
views
Sigma proofs for Pedersen commitments arithmetic under different bases
I was wondering if it's possible to prove an equality of openings between $3$ Pedersen commitments $P\cdot Q$ and $R$ when $P, Q, R$ have different commitment keys.
Suppose that commitment $R$ commits ...
- 548
4
votes
1
answer
444
views
Zk-SNARK against Sigma Protocols and for Secure Function Evaluation
I have a couple of questions on ZK-SNARK:
Based on what I understand, a ZK-SNARK is an "Argument of knowledge". That means that it should be equivalent to Sigma Protocols like Fiat-Shamir and ...
- 177
2
votes
2
answers
606
views
Sigma protocol with Pedersen commitment and Hash function
Suppose I construct a Pedersen commitment as $g^m h^r$. I could pick the randomness in a "pseudo-random" fashion, such that $r = H(m)$. My questions are as follows:
Given that $H$ is collision-...
- 314
8
votes
1
answer
558
views
Sigma protocol when order is unknown
In the following paper (page 5) they have a proof that a triple $\left(g,b_{i-1},b_{i}\right)$ is of the form: $\left(g,g^{x},g^{x^{2}}\right)$ for some x.
The relevant text from the paper is as ...
- 209
2
votes
1
answer
290
views
Challenges of Fiat-Shamir Transformation of ZK Proof / Sigma Protocol
Let $\Sigma$ be a sigma protocol whose commitment, challenge and response phases are $\Sigma_1, \Sigma_2, \Sigma_3$, respectively.
In Fiat-Shamir Transformation, the challenges are $H(\Sigma_1)$ ...
- 325
1
vote
0
answers
97
views
Sigma Protocol with Privacy-preserving Discrete Logarithms?
I've been reading up on Sigma Protocols and Fiat-Shamir Heuristic. There is a small problem I see here that is possibly already solved, but I'd like to know if it has a solution.
Peggy wants to prove ...
- 177
4
votes
1
answer
248
views
Are multi move proof protocols still "sigma protocols"?
Conventionally, sigma protocols are defined as being a three-move protocol (1. commit, 2. challenge, 3. response). Reading papers like "Bulletproofs" (Bunz, Bootle, Boneh et al., 2018), it feels like ...
- 2,320
2
votes
1
answer
200
views
Honest Verifier Zero-Knowledge Game for Sigma Protocols
I am looking for how an adversary to special HVZK would work. In Boneh and Shoup's book (BonehShoup) they have Attack Game 20.4 for special cHVZK.
Here, the adversary produces a pair (x,y) (witness ...
- 395
1
vote
0
answers
408
views
Need tips on how to break Fiat-Shamir sigma-protocol (programming challenge)
I'm completely stuck on an university programming challenge and I need some tips to get me out of the valley I'm in, you don't need to give the full answer if you do not wish to.
What we have:
Fiat ...
- 23
4
votes
1
answer
989
views
Fiat-Shamir transform to Sigma protocols to turn into NIZK
I'm reading about the Schnorr's zero-knowledge proof for DLOG and the Sigma protocol for DH tuple proof, and I want to know how one applies Fiat-Shamir transform to both of them, to turn them into ...
user4936
6
votes
2
answers
584
views
Is this Sigma Protocol zero knowledge or is it just a proof of knowledge?
Suppose I have the witness $x$ and need to prove that I correctly computed $(g^x)^x$ to a verifier. $g$ and $g^x$ are public. The verifier asks me for $(g^x)^x$, but wants proof that I've given them ...
- 438
1
vote
0
answers
132
views
Sigma protocol compiler?
Is there a well maintained, preferably documented, Sigma protocols compiler library? i.e. takes an abstraction of statements to prove, and outputs a cryptographic protocol between verifier and prover? ...
- 377
4
votes
3
answers
1k
views
Sigma protocol for AND-composition involving the same secret
Say we have two public cyclic groups $G_1$, $G_2$ of corresponding prime orders $p_1$, $p_2$, and known generators $g_1$, $g_2$.
Say $g_3$ is also a generator of $G_2$.
For publicly known $C_1$ and $...
- 377
0
votes
1
answer
334
views
Sigma protocol ZK-proof of a pair of pedersen commitments
Let's say you are using a $\Sigma$ protocol ZK proof to prove knowledge of $x_1, x_2$ so that $Y = g_1^{x_1}g_2^{x_2}$. Of course $g_1$, $g_2$ are generators within cyclic group G of prime order q, ...
1
vote
1
answer
389
views
Disjunction of several instances of sigma protocol
Assume there exists zero-knowledge interactive protocol for a language $L \in NP$ i.e., if an instance $x \in L$ then prover can convince the verifier, that $x \in L$ with high probability without any ...
- 889
1
vote
1
answer
401
views
Proving Sigma Protocol on a Schnorr Protocol Variant
Let p, q be chosen as in Schnorr's protocol, and let $g_1, g_2, h$ be elements in $Z^*_P$ of order q.
Assume that the prover P gets as input $w_1,w_2$ where $h = (g_1^{w_1}g_2^{w_2}) \mod q$.
...
- 365
1
vote
1
answer
720
views
Sigma protocol to prove that the prover knows how open a commitment
Sigma protocol to prove that the prover knows how open a commitment.
Consider the unconditionally hiding commitment scheme based on discrete log, i.e., the public key $p_k = (p,g,y)$, where $\langle ...
- 321
3
votes
1
answer
207
views
Sigma protocol: witness hiding
I am working on an assignment and I am stuck with the last part of proving witness hiding for the protocol.
I have previously proved it is witness indistinguishable, and it has q (primer number ...
- 31
8
votes
2
answers
1k
views
What is an example of a secure sigma proof?
I want to implement Threshold Elgamal as described in section 6.3.1 and in the decryption phase each party must broadcast a sigma proof to show that it actually has a valid secret share of the secret ...
- 681
3
votes
1
answer
845
views
Sigma-protocol for 3SAT problem
I have some questions from previous years exams, I hope you could help me with them. :)
Let $g,h$ denote generators of a group $G$ of large prime order $n$ such that $\log_g h$ is unknown to anyone. ...
3
votes
0
answers
340
views
Transforming simplest protocol into a Sigma-protocol
I have some questions from previous years exams, I hope you could help me with them. :)
Suppose that a protocol satisfies the properties of a $\Sigma$-protocol, except that it is only (plain) ...