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,020
questions
0
votes
0
answers
22
views
Why the full r-torsion group contains r^2 many elements and consists of r+1 subgroups
let F be a finite field, E(F) an elliptic curve of order n, ...
- 101
2
votes
0
answers
21
views
knowledge soundness in IVC paper
In "On Defining Proofs of Knowledge" by Mihir Bellare and Oded Goldreich, the definition of knowledge soundness (KS) is (See Definition 3.1):
Validity (with error $\kappa$): Let $p(x)>\...
- 121
0
votes
1
answer
45
views
which zero knowledge proof technique is suitable for identity verification system?
I am a beginner in the cryptographic field but as a graduation project, I have to build an identity verification and management system using zero-knowledge proofs.
I see a lot of zkp techniques, ...
- 1
0
votes
0
answers
35
views
Zero Knowledge 3-coloring, but we allow malicious V to challenge two edges
So I think I understand how zero knowledge protocol with 3-coloring is supposed to work. But in an attempt to increase soundness of the protocol, we allow the verifier V to challenge two edges per ...
0
votes
0
answers
28
views
How can I determine if the result of subtracting two Pedersen commitments is negative or positive?
I'm using Pedersen commitments to maintain the account balance in the ledger.
Assume that when I create the account, I record the Pedersen commitment of 0 in a ledger (here, the blinding factor and ...
- 21
2
votes
1
answer
76
views
Use zk-STARK for post-quantum signature scheme?
Could you not use zk-STARK for a post-quantum signature scheme?
Your private key is a random symmetric encryption key, your public key is the hash of the encryption key.
To sign you run an algorithm ...
- 169
1
vote
0
answers
20
views
How to convert Lattice based signature to R1CS statements?
How can we convert a lattice-based signature (like based on Fiat Shmair with abort e.g. Dilithium) to R1CS?
2
votes
0
answers
42
views
How can we combine circuits for complex ZKBoo proofs?
I'm a bit lost. I know that ZKBoo can be used for proving $y = C(x)$ for any boolean or arithmetic circuit $C$. However, I'm unsure how to combine several circuits when we want to do more complex ...
- 548
0
votes
0
answers
30
views
Is the NIZK constructed based on Pedersen commitment transparent?
It is well-known that, in the setup phase of Pedersen commitment, it is necessary to generate $g,h\in G$. Then a user can compute $c = g^vh^r$ to commit the value $v$.
Is a trusted center needed to ...
- 63
1
vote
0
answers
25
views
If a SoK satisfies simulatability and extractability, is this signature unforgeable and non-malleable?
This paper[1] defines the simulatability and extractability of the signature of knowledge (SoK).
As is widely known, a secure signature scheme should be both unforgeable and non-malleable. Can we ...
- 63
0
votes
1
answer
65
views
Can a Sigma protocol be transformed into a signature of knowledge through Fiat-Shamir transform？
As is well known, a sigma protocol can be transformed into a NIZK protocol through a Fiat-Shamir transform.
But can the Sigma protocol be transformed into a signature of knowledge in a similar manner?
...
- 63
2
votes
1
answer
64
views
In NIZK, what is the difference between "transparent“ and “without trusted setup”?
When I study a zk-SNARK scheme, the scheme claims to be transparent. Does this mean that this scheme does not require a trusted setup? Furthermore, if a NIZK scheme includes a Common Reference String (...
- 63
1
vote
0
answers
99
views
Zero Knowledge Proof for SHA-256 preimages [duplicate]
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
73
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
20
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
72
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
91
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 ...
- 227
1
vote
1
answer
42
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
3
votes
3
answers
246
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
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
112
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
57
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
27
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
44
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,169
1
vote
0
answers
30
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
125
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
52
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 ...
- 73
1
vote
1
answer
66
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,169
1
vote
1
answer
107
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,169
0
votes
0
answers
29
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
135
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
68
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
29
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
98
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
54
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,169
2
votes
1
answer
58
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
191
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
82
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
148
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
80
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....
- 133
2
votes
0
answers
91
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
88
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
130
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,169
0
votes
1
answer
96
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
67
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
43
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
216
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
53
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
42
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