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.
1,014
questions
1
vote
0
answers
80
views
Zero Knowledge Proof for SHA-256 preimages
I need to design some protocol where actors will leverage Zero Knowledge Proofs (ZKP) to prove that they know the pre-image of some specific SHA256 hash without revealing the pre-image itself.
Ideally,...
1
vote
2
answers
63
views
Zero Knowledge Argument for Elliptic Curve Multiplication/Inverse Multiplication Correctness?
I was reading this post and the accepted answer wrote about a way to “prove that some list of points $[A,B,C,...]$ when multiplied by $x$ produces $[A′,B′,C′,...]$”. However, in their explanation ...
0
votes
0
answers
18
views
Question on Aleo zkVM
Can we use array as the input of a transition/function? Just like:\
transition testarr(arr: [u32; 3]) {
}
I saw some tutorials that have examples of this but now ...
- 61
1
vote
3
answers
58
views
Zero-Knowledge Proof of Encryption with a Specific Key
Short version:
Given a hash of a plaintext, a public key, and a ciphertext (but not knowing the original plaintext), is there any way to verify that the ciphertext is the plaintext after being ...
- 111
1
vote
1
answer
85
views
Encryption scheme with variable and provable key-length
I'm currently studying the possibility of a novel ransomware technique, where an adversary instead of forcing the victim to pay a ransom, forces them to brute force a key of given length and thus ...
- 229
1
vote
1
answer
37
views
Amplifying the completeness and soundness of a proof scheme
A (interactive) proof system for a language $\mathcal{L}$ is defined by two algorithms $\mathcal{P}$, a prover, and $\mathcal{V}$, an efficient verifier, with the following requirements:
Completeness:...
- 445
2
votes
2
answers
200
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 ...
- 340
0
votes
0
answers
25
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
106
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
44
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 ...
- 413
1
vote
0
answers
19
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 ...
- 31
1
vote
0
answers
43
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,167
1
vote
0
answers
26
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
122
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
45
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
0
votes
1
answer
41
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 ...
- 53
1
vote
1
answer
55
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,167
1
vote
1
answer
91
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,167
0
votes
0
answers
19
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
128
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
2
votes
0
answers
58
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 ...
- 143
1
vote
1
answer
27
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
87
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
51
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,167
2
votes
1
answer
48
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
155
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
79
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
124
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
74
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....
- 113
2
votes
0
answers
88
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 ...
- 122
0
votes
1
answer
64
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
126
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,167
0
votes
1
answer
52
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
58
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
37
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
174
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 ...
- 143
0
votes
2
answers
52
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
38
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
46
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
174
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
99
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,167
0
votes
1
answer
111
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 ...
- 122
2
votes
1
answer
104
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]//...
- 31
2
votes
1
answer
65
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
82
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
40
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,167
0
votes
0
answers
15
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
53
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 ...
- 58
0
votes
1
answer
97
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
15
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