Skip to main content

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.

Filter by
Sorted by
Tagged with
1 vote
0 answers
341 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 ...
artificial_inspector's user avatar
0 votes
1 answer
103 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 $...
user105684's user avatar
1 vote
2 answers
270 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\...
user105684's user avatar
1 vote
2 answers
101 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....
Kolja's user avatar
  • 143
2 votes
0 answers
95 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 ...
Paul Yu's user avatar
  • 156
0 votes
1 answer
339 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 ...
alygg's user avatar
  • 1
0 votes
2 answers
153 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 ...
user93353's user avatar
  • 2,160
0 votes
1 answer
225 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
questionman123's user avatar
1 vote
1 answer
94 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 ...
Dani Vilardell's user avatar
0 votes
0 answers
53 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 ...
Matan Shtepel's user avatar
4 votes
1 answer
425 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 ...
JP.'s user avatar
  • 165
0 votes
2 answers
67 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 ...
learner1's user avatar
0 votes
1 answer
48 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 ...
Stent's user avatar
  • 5
0 votes
0 answers
59 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 ...
Peersky's user avatar
1 vote
0 answers
197 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 ...
rapt's user avatar
  • 91
1 vote
1 answer
134 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 ...
user93353's user avatar
  • 2,160
0 votes
1 answer
129 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 ...
Paul Yu's user avatar
  • 156
2 votes
1 answer
147 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]//...
user109993's user avatar
2 votes
1 answer
187 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 ...
Jason L. B.'s user avatar
1 vote
0 answers
87 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 ...
Ethan's user avatar
  • 121
1 vote
0 answers
70 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 ...
Alex Them's user avatar
  • 322
0 votes
1 answer
158 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 ...
tesoke's user avatar
  • 181
2 votes
0 answers
89 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),...
tesoke's user avatar
  • 181
1 vote
2 answers
230 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 ...
Joe Rowell's user avatar
3 votes
1 answer
352 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 ...
Ilk's user avatar
  • 233
3 votes
1 answer
150 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 ...
tock203's user avatar
  • 345
2 votes
0 answers
39 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 ...
John dow's user avatar
  • 149
1 vote
0 answers
105 views

Is the Lemma4.5 in the Plonk paper correctly described?

In lemma4.5, of PlonK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge they claim that we can construct a polynomial protocol $P^*$ with an $S$-ranged polynomial ...
mactep Cheng's user avatar
1 vote
0 answers
99 views

Proving set membership using Plonky2 [closed]

I'm not sure if this is a good place to ask, but I have some issues with using plonky2 to make some proof. In particular, I want to prove that a private element is part of a set (i.e. $x \in X$), and ...
Benjamin V's user avatar
1 vote
0 answers
90 views

What are the computational limitations of ZkProofs using ZoKrates?

I'm trying to create a zk-proof of a neural network in https://github.com/berendjan/zk-neural-network using ZoKrates and PyTorch. The steps to reproduce are in the README.md However, when computing ...
blanNL's user avatar
  • 111
2 votes
1 answer
139 views

Deterministic EC key derivation with anonymity and proofs

Following up this question There are 4 parties: Alice, who needs to prove a posession of some statement $m$, unique to her, say a street address, which is basically a string of some predefined format,...
John dow's user avatar
  • 149
2 votes
1 answer
145 views

Can a 3-coloring for a graph be represented as a circuit?

I was looking at a layman explanation for zero-knowledge proofs in zk-SNARKs here. The idea there is that if one knows a solution (3) to a question (find a value of ...
user1936752's user avatar
3 votes
1 answer
153 views

Division of two Elliptic curve points in KZG polynomial commitment scheme!

I have some issue to understand the verify round of the KZG polynomial commitment scheme. The following diagram is associated to the scheme. I appreciate any help. To verify, the verifier should ...
tesoke's user avatar
  • 181
3 votes
1 answer
188 views

PLONK: Why is the quotient polynomial multiplied by different powers of a challenge?

From the PLONK paper. Page 29, Round 3 The paper doesn't explain the need or the use of the quotient challenge $\alpha$. I understand why each of the polynomials is multiplied by $\frac {1}{Z_H}$ but ...
user93353's user avatar
  • 2,160
3 votes
1 answer
71 views

What does preprocessed polynomial mean in the context of PLONK?

The PLONK paper uses the term preprocessed polynomial a lot of times. For e.g. page 14 The protocol definition includes a set of preprocessed polynomials $g1, . . . , g_l \in F<d[X]$ Page 20 ...
user93353's user avatar
  • 2,160
5 votes
1 answer
94 views

Securely derive multiple EC keys from master EC key and prove it

Alice has master EC key pair: $a$ - private key, $A$ - corresponding public key Bob generates 2 random integers $r_1$ and $r_2$ and wants Alice to derive 2 new key pairs: $a_1$ = $a$ + $r_1$ and $a_2$ ...
John dow's user avatar
  • 149
2 votes
1 answer
117 views

Is the permuation check range in the PLONK Paper incorrect?

From the PLONK paper. On pages 19 & 20, the paper describes the prescribed permutation check in PLONK. ---------------------------------------------------------------------------------------------...
user93353's user avatar
  • 2,160
1 vote
1 answer
104 views

Ensure deniability of an interactive zero knowledge proof

Suppose that Peggy(prover) and Victor(verifier) are running some zero knowledge proof protocol that does not rely on hidden verifier secrets. The verifier generates randomly chosen challenge values ...
Richard Thiessen's user avatar
1 vote
1 answer
173 views

Question about the PLONK permutation check

From the PLONK paper. On pages 19 & 20, the paper describes the prescribed permutation check in PLONK. In the last step of the proof, these are the checks a) $L_1(a)(Z(a) - 1) = 0$ b) $Z(a)f'(a) =...
user93353's user avatar
  • 2,160
1 vote
1 answer
175 views

How exactly bilinear pairing multiplication in the exponent of g is used in zk-SNARK polynomial verification step?

I am reading this explanation of zkSnark written by Maksym Petkus - https://arxiv.org/pdf/1906.07221.pdf In page 24, the zk-SNARK of polynomial is explained. In setup phase, the proving and ...
INDUKURI MANI VARMA 21911012's user avatar
2 votes
1 answer
116 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
1 vote
0 answers
60 views

How can we explain STARK with less math?

I am trying to understand STARK with not much math. I understand SNARK like this: Computation → Arithmetic Circuit → R1CS → QAP → zk-SNARK From the helpful article: https://z.cash/technology/zksnarks/ ...
manu muraleedharan's user avatar
1 vote
2 answers
152 views

Where can I find 2 of the steps/proofs described in Dan Boneh's video on PLONK in the PLONK Paper? The 2 don't seem to match

This is Dan Boneh's video on PLONK - https://www.youtube.com/watch?v=vxyoPM2m7Yg I went through the video multiple times & also tried to go through the original PLONK paper - https://eprint.iacr....
user93353's user avatar
  • 2,160
1 vote
0 answers
30 views

Why do we need the random number in Pinochioo protocol compared with GGPR

I find it hard to fully grasp the whole Pinocchio protocol . I understand that the $\alpha$ s are for restricting the prover to compute only the corresponding set-up values. But it's not clear for me ...
Wang Linger's user avatar
1 vote
0 answers
58 views

Best Practices for Writing Prover and Verifier Circuits for Zero-Knowledge Proof Implementation

Considering that I am writing a circuit that will take age as input and return true or false. For this ZKP system, I guess I don't need a separate prover circuit and verifier circuit. Consider that I ...
Tanjin Alam's user avatar
2 votes
0 answers
80 views

To prove equality/inequality of plaintexts of 2 ciphertexts encypted under different encryption schemes

We have 2 ciphertexts, one encrypted using Paillier and another encrypted under Elgamal encryption schemes. Is there a way to design ZK-proof to prove equality of the underlying plaintexts of these 2 ...
G Pavithra 's user avatar
2 votes
0 answers
22 views

How to choose the value of state width of Plonk with lookup?

I noticed that it seems the original Plonk paper introduced that there were two extensions with state width = 3 or 4 (as described in https://github.com/matter-labs/proof_system_info_v1.0/blob/master/...
CryptoLover's user avatar
2 votes
1 answer
54 views

Can we pad witness of bulletproof and dory to be exponential size?

Bulletproof and dory reduce the witness size by a half during each interaction, until the witness is compressed to be only one element. But what about the witness is not precisely exponential size? ...
Walker's user avatar
  • 61
1 vote
1 answer
61 views

ZKP vs disposable addresses [closed]

In other words, what does ZKP brings on top of the practice of not reusing addresses? From my research, ZCash is currently a state of the art example of ZKP application, but what extra benefits does ...
Jp_'s user avatar
  • 111
3 votes
1 answer
97 views

How do I construct a recursive polynomial as required in PLONK?

I am going through Dan Boneh's video on PLONK - https://www.youtube.com/watch?v=LbpPCN-f_XA&t=952s At around 19 minutes, he gets to the Prod Check Gadget. Background: $\omega \in F_p$ is the ...
user93353's user avatar
  • 2,160

1 2
3
4 5
22