Skip to main content

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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
37 views

Can ring signatures be considered as non interactive set membership proofs?

Can ring signatures be considered as non interactive set membership proofs? For example, if the message msg is set to null, can the ring signature scheme proposed by Rivest et al. be regarded as a non ...
user109993's user avatar
1 vote
1 answer
60 views

Showing special soundness for Dilithiums underlying $\Sigma$-protocol

I'm trying to prove the security of Dilithiums underlying $\Sigma$-protocol using the following theorem. Let $\Sigma=\left(\mathcal{P},\mathcal{V}\right)$ be a $\Sigma$-protocol on an effective ...
limeeattack's user avatar
4 votes
1 answer
82 views

Security impact of weakened collision resistance for 128-bit Fiat-Shamir challenges

As I understand, to achieve a security level of $\lambda$, a hash function's output should be at least $2\lambda$ in length, since the search space is halved for collision resistance. However, I am ...
Taka's user avatar
  • 43
0 votes
1 answer
123 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 $\...
Cristian Baeza's user avatar
0 votes
0 answers
47 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 ...
Lev's user avatar
  • 468
2 votes
1 answer
113 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 ...
pintor's user avatar
  • 558
2 votes
2 answers
417 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?
George Herbert's user avatar
0 votes
0 answers
226 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?
user1850484's user avatar
1 vote
1 answer
78 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 ...
eternalmothra's user avatar
2 votes
1 answer
275 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 ...
wattlab's user avatar
  • 21
3 votes
1 answer
328 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 ...
cadaniluk's user avatar
  • 229
0 votes
3 answers
301 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 ...
user1794567's user avatar
0 votes
1 answer
85 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 ...
joakimb's user avatar
  • 243
4 votes
2 answers
570 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 ...
pintor's user avatar
  • 558
4 votes
1 answer
565 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 ...
jimmytann's user avatar
  • 177
2 votes
2 answers
657 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-...
Panos's user avatar
  • 324
8 votes
1 answer
611 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 ...
yacovm's user avatar
  • 209
2 votes
1 answer
303 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)$ ...
Leafar's user avatar
  • 325
1 vote
0 answers
103 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 ...
jimmytann's user avatar
  • 177
4 votes
1 answer
285 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 ...
Ruben De Smet's user avatar
2 votes
1 answer
225 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 ...
eternalmothra's user avatar
1 vote
0 answers
419 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 ...
Akke's user avatar
  • 23
4 votes
1 answer
1k 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 ...
user avatar
6 votes
2 answers
640 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 ...
fraiser's user avatar
  • 438
1 vote
0 answers
136 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? ...
oleiba's user avatar
  • 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 $...
oleiba's user avatar
  • 377
0 votes
1 answer
347 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, ...
ElectronicToothpick's user avatar
1 vote
1 answer
423 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 ...
preethi's user avatar
  • 889
1 vote
1 answer
417 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$. ...
Jjang's user avatar
  • 365
1 vote
1 answer
755 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 ...
Shuzheng's user avatar
  • 321
3 votes
1 answer
228 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 ...
Nohr's user avatar
  • 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 ...
guglielmo london's user avatar
3 votes
1 answer
869 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. ...
Peter De Vries's user avatar
3 votes
0 answers
343 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) ...
Peter De Vries's user avatar