Questions tagged [zero-knowledge-proofs]
Zero-knowledge proofs are an interactive method for one party to prove to another that a statement is true, without revealing anything other than the veracity of the statement.
121
questions
3
votes
3
answers
286
views
State of the art for Graph Isomorphism
I want to know the state of the art result for proving knowledge of graph isomorphism. As described here, the classical Goldreich-Micali-Wigderson (GMW) protocol is a $\Sigma$-protocol with soundness ...
- 350
0
votes
0
answers
42
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 ...
- 443
2
votes
1
answer
122
views
Statistics-heavy crypto papers
I'm currently taking a course in which we choose a stats-heavy paper and analyse it, summarising our work in the form of a written report and presentation. I have tried to find such a paper in crypto, ...
1
vote
1
answer
99
views
Unbounded distinguishers and statistical indistinguishability
In constructing a SHVZK simulator for a sigma protocol I am working on I have encountered some fairly basic questions, but ones which are not often discussed in textbooks and papers - consider the two ...
- 443
1
vote
0
answers
37
views
How can the validity of signatures in layer-2 transactions be proven in zk-rollup?
I have many questions about the details of using zk-SNARK technology in zk-rollup：
How can the validity of signatures in layer-2 transactions be proven in zk-rollup?
In zk-rollup, is a single large ...
- 63
1
vote
0
answers
45
views
How do we represent a Gate involving a constant to the left or right of the operator in PLONK?
Let's say I have the following equation to be arithmetised in PLONK
$x^3 + x + 5 = 35$ and the witness is $x = 3$
$3 * 3 = 9$
$9 * 3 = 27$
$27 + 3 = 30$
$30 + 5 = 35$
Now the 4th gate can be expressed ...
- 2,213
1
vote
0
answers
37
views
Disjunctive ZK Proof of knowledge of discrete log
I want to construct a non-interactive ZK proof that in a set of pairs of group (where the DDH-assumption holds true) elements:
$(g_1, Y_1), (g_2, Y_2), ..., (g_n, Y_n)$
, the prover knows at least one ...
- 21
2
votes
0
answers
147
views
Equality of ElGamal plaintext & Pedersen commitment message
Let's imagine two entities: Bob and Alice. Bob's public key is $B = bG$. Alice's public key is $A = aG$.
Alice encrypts her number $n$ with Bob's public key so Bob could decrypt it ($n$ is small ...
- 33
0
votes
0
answers
48
views
Zero-Knowledge Proof to prove hash of plaintext without decrypting [duplicate]
I'm decently new to cryptography and am trying to wrap my head around zero-knowledge proofs and applications. One use case that I am trying to figure out a strategy for is the following:
I have some ...
- 101
1
vote
1
answer
74
views
Practical feasibility of proving a plaintext hash relationship with a zk-SNARK
I am interested in the practicality of using generic SNARK techniques to prove the following relation.
Let E and E' be two ...
- 83
1
vote
1
answer
85
views
Where & how is the 2nd group used in the KZG Commitment Scheme in case the 2 groups are not the same?
This is about the KZG Polynomial Commitment Scheme
In Section 2, it's written
We use the notation $e : \mathbb G \times \mathbb G \mapsto \mathbb G_T$ to denote a symmetric (type 1) bilinear pairing....
- 2,213
2
votes
1
answer
145
views
PLONK's computation of the first Lagrange polynomial at $\zeta$
From the PLONK paper.
On Page 31, Point 6
Compute the Lagrange Polynomial Evaluation $L_1(\zeta) = \frac{\omega(\zeta^n - 1)} {n(\zeta- \omega)}$
I don't think this formula is correct.
We have $n$ ...
- 2,213
0
votes
0
answers
38
views
What is the running time of precomputation for the PLONK zk-SNARK?
I have been looking for benchmarks on the precomputation phase of PLONK (https://eprint.iacr.org/2019/953.pdf), but found none. Is there a resource where one can get a feel for this? Either in terms ...
- 243
1
vote
1
answer
144
views
Many-out-of-many proofs
I need to prove that given vector of commitments of length N contains N-1 commitments to zero (and one to an arbitrary number).
More formally, given vector:
$$\textbf{a} = \begin{bmatrix}
C(0, r_1)...
- 33
3
votes
1
answer
157
views
Fischlin vs. Fiat-Shamir Performance
Using Fiat-Shamir, an interactive 3-round sigma protocol can be compiled into a non-interactive zero-knowledge proof in the random oracle model.
A NIZK through Fiat-Shamir is not UC-Secure due to ...
- 155
1
vote
1
answer
39
views
Is it possible to forge valid proofs in this Schnorr signature-based ZKP system for proving knowledge about discrete logarithms?
I am currently reading the paper "A 2-round anonymous veto protocol" and have run into some trouble verifying the claims made about the zero knowledge proofs presented within. My knowledge ...
- 13
2
votes
1
answer
127
views
Prove with ZKP that I have encrypted a message $v + random\_number\cdot c$ given an RSA public key?
I want to create an application in which users can cast vote to blockchain in encrypted form using RSA. The private key will be revealed only after completion of the election.
My major use case is as ...
- 71
0
votes
1
answer
62
views
Why does the permutation polynomial have the First Lagrange base added to it in PLONK?
From the PLONK paper.
On page 19 & ahead, the permutation check is described.
In particular, on page 20, the protocol is described.
Step 5 of the check is described as
Verifier checks if for all $...
- 2,213
2
votes
1
answer
82
views
How to convert exponents and group operations to gates in arithmetic circuit
I am following Vitalik Buterin's article to study zk-SNARKs recently.
I can understand the main procedure of zk-SNARKs when given example equation x**3 + x + 5 == 35. However, in cryptography, most ...
- 185
1
vote
0
answers
274
views
ZK-STARK soundness
I've been reading about ZK-STARK. There's an example that appears in several blogs. The most detailed explanation of that specific example which I have found so far is in this blog.
The description of ...
0
votes
1
answer
92
views
Given pedersen commitments of some elements, how to prove that the sum of only one subset of these elements is equal to the given element θ？
Assume that Prover have $n$ pedersen commitments ($V_{a_1},V_{a_2},\cdots,V_{a_n}$ where $V_{a_i}=G \cdot a_i + H \cdot r_{a_i}$) of $n$ elements $a_1,a_2,\cdots,a_n$. The Prover have another element $...
- 11
1
vote
2
answers
210
views
How to prove that a Pedersen commitment has the same value as at least one of a set of other Pedersen commitments, without revealing which
A prover has two pedersen commitments, $V_{a}=G\cdot a+H\cdot r_a$ and $V_{b}=G\cdot b+H\cdot r_b$, which commit the values $a$ and $b$ respectively.
The prover has another commitment $S_{\sigma}=G\...
- 11
1
vote
2
answers
90
views
Proving addition of secret values in a small field
Suppose that a prover holds two secret values $x,y\in\mathbb{F}$ and both the prover and verifier have $z\in\mathbb{F}$. The prover wishes to prove that $z=x+y$ without revealing $x,y$ to the verifier....
- 143
2
votes
0
answers
93
views
PLONK: Rationale Behind Specific Polynomial Evaluations in Round 4
In round 4, protocol evaluates a(zeta), b(zeta), c(zeta), Sσ1(zeta), Sσ2(zeta). I know linearisation trick in round 5 implies the identity of other terms. Can we ...
- 156
0
votes
1
answer
274
views
R1CS and zkSNARK
so recently I've been exploring zk-SNARKs algorithm, and I have a maybe stupid question. For example, let's take $x^2+x+1$ and make an algebraic circuit from it:
$y=x*x$
$sum=x+1$
$out=sum+y$
(First ...
- 1
0
votes
2
answers
146
views
PLONK: Reducing the number of Field Elements Trick
From the PLONK paper.
Page 18
We describe an optimization by Mary Maller to reduce the number of $F$-elements in the proof from $M$. We begin with an illustrating example. Suppose $V$ wishes to check ...
- 2,213
0
votes
1
answer
162
views
PCD vs Recursive SNARK vs Non-uniform IVC
I was wondering if anyone could clarify the differences between PCD vs Recursive SNARKs(like pickles) vs Non-uniform IVC(like hypernova)
They all seem very similar to me
1
vote
1
answer
85
views
Is it possible to batch ZKP proofs from different polynomials but same point?
According to the ZKP MOOC lecture by Dan Boneh, it is possible to batch proofs from different polynomials and different points into a single group element:
Nonetheless, I haven't been able to find ...
- 140
0
votes
0
answers
50
views
A cryptographic proof system which uses rewinding to argue soundness but is not a proof of knowledge?
Are there any cryptographic proof systems that rewind the prover to argue soundness but are not proofs of knowledge? In particular, I would be very curious to see examples of proof systems where ...
4
votes
1
answer
339
views
Zero-knowledge card shuffle
I'm trying to design a zero-knowledge protocol for the creation of a shuffled deck of cards for use by two players. Naturally this requires that neither player knows the order of the cards after the ...
- 163
0
votes
2
answers
64
views
Proof generation in zk cryptocurrency
In a cryptocurrency with privacy e.g., zcash, where does proof generation take place? Can it happen in the client's device every time a transaction is performed?
If it happens in client's device, are ...
- 1
0
votes
1
answer
44
views
Is there a SNARK system that will give the same proof bytes for different witnesses?
Suppose the circuit is a hash function with the input being the pre-image (private) and the output being the digest (public). If one knows of a collision can they create 2 different proofs that are ...
- 5
0
votes
0
answers
56
views
Is it posible to generate SNARK of MPC share validity?
Assume we have a central issuing authority that sends each participant a share that reconstructs in key $P_k$. I.e. Shamir Secret Share with $2$ out of $N$ format where $N>3$.
This central ...
- 1
1
vote
0
answers
192
views
Quantum-safe algorithm for hiding cryptocurrency transaction amount [closed]
I have a decentralized coin system that I am trying to develop.
Each coin can be split up into 1,000,000 units.
I've been looking for a quantum-safe and practical (efficient) algorithm to send ...
- 91
1
vote
1
answer
128
views
Unable to understand Eli Ben Sasson's STARK arithmetization & proof example
This is from this video - https://www.youtube.com/watch?v=9VuZvdxFZQo
Bob has a list of length $10^6$. Bob wants to convince Alice that every number in the list is between 1 & 10. Alice needs to ...
- 2,213
0
votes
1
answer
123
views
The Multiplication of z(x) and z(Xw) in the Quotient Polynomial from the PLONK
From the PLONK paper.
Page 29, Round 3
Why multiply z(x) and z(Xw) in the quotient polynomial? (why does internal wiring have to multiply input permutation)
Why the second term have to "shift by ...
- 156
2
votes
1
answer
137
views
How to prove the correct decryption of several (ElGamal) ciphertexts in a batch？
I know how to prove the correct decryption of a (ElGamal) ciphertext.
The above protocol is from the paper: Bootle J, Cerulli A, Chaidos P, et al. Short accountable ring signatures based on DDH[C]//...
- 63
2
votes
1
answer
169
views
Parameters needed for Chaum-Pedersen Protocol
I've came across a Stackexchange question about the Chaum-Pedersen Protocol which is based on the generalised schnorr protocol. As I understand it, it uses discrete logs and cyclic groups of prime ...
- 21
1
vote
0
answers
85
views
How many pairings are needed to verify beta term in GGPR13 zk-snark? Pinocchio paper says 3 but I count 4
The Pinocchio paper contains a description of the GGPR protocol (Protocol 1), and states that verification requires "8 pairings for the $\alpha$ terms, and 3 for the $\beta$ term". However I ...
- 121
0
votes
0
answers
48
views
The PLONK Gate constraint equation seems to designed more for accomodating adding a constant in a Gate but not multiplying with a constant
From the PLONK paper.
Page 23, 6 Constraint System
The constraint system $C = (V, Q)$ is defined as follows.
$V$ is of the form $V = (a, b, c)$, where $a$, $b$, $c \in [m]^n$. We think of $a$, $b$, $...
- 2,213
0
votes
0
answers
18
views
Group keys with revocation in publish/subscribe IoT
I have a group of subscribers who are subscribed to a message broker in an IoT setting, let's say to the topic 'sensor/temperature'. Now, I want to create a public/private key pair in such a way that ...
1
vote
0
answers
62
views
Authors of "How to explain zero-knowledge Protocols to your children?"
Does anyone know what are the family relationships in the paper "How to Explain Zero-Knowledge Protocols to Your Children"
The authors are: Jean-Jacques Quisquater, Myriam Quisquater, Muriel ...
- 68
0
votes
1
answer
144
views
Verification in Bulletproof commitment scheme
I am reviewing the ZKP course, represented by the university of Berkley (https://zk-learning.org/). In pages 44 of lecture 6 that is attached below (https://zk-learning.org/assets/lecture6.pdf), the ...
- 181
0
votes
0
answers
20
views
Ephemeral anonymous identities that can be slashed once forever with a single nullifier
Consider a ZKP anonymous credential scheme where each tuple of (x, identity_secret, merkle_root) corresponds to a unique nullifier computed as ...
- 1
0
votes
0
answers
91
views
After ZK-shuffle, how can we let people who got the same number card know each other without letting anyone else know?
In mental poker, we can use ZK-shuffle to deal cards to the players such that the cards are kept private to each player (https://hackmd.io/@nmohnblatt/SJKJfVqzq). Suppose we deal exactly one card to ...
- 101
2
votes
0
answers
83
views
Poly-commitment based on Bulletproofs
I am reviewing the ZKP course, represented by the university of Berkley (https://zk-learning.org/). In pages 41 and 42 of lecture 6 that is attached below (https://zk-learning.org/assets/lecture6.pdf),...
- 181
1
vote
2
answers
200
views
Is there a ZKP that proves knowledge of a particular elliptic curve point?
Let E be an elliptic curve of prime order n. If we assume that Alice and Bob both know a scalar value ...
- 11
3
votes
1
answer
335
views
Assumptions on zero-knowledge proofs without trusted setup
Let's start with what got me wondering about this issue:
It's a curious construction, that while most digital signature schemes come from public-key encryption (Impagliazzo's cryptomania), there are ...
- 233
3
votes
1
answer
122
views
Verify HMAC tag without knowing the key
Let's say there's Alice and Bob.
Let Alice and Bob agree on a message $M_1$, a tag $T_1$, and a function $HMAC$.
Alice proves to Bob that she knows a key $K$ such that $T_1 = HMAC(M_1, K)$ without ...
- 345
2
votes
0
answers
38
views
ZKP of knowledge of EC keys preimage
There is a random scalar seed $s$ which we may call a master secret.
There are 2 public strings or scalars: $m1, m2$ and 2 corresponding EC keypairs: $a, A=a*G$ and $b, B=b*G$
$a$ and $b$ are somehow ...
- 149