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,076 questions
Filter by
Sorted by
Tagged with
1 vote
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 ...
103 views

1 vote
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....
• 143
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 ...
• 156
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 ...
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 ...
• 2,160
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
1 vote
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 ...
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 ...
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 ...
• 165
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 ...
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 ...
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 ...
1 vote
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 ...
• 91
1 vote
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 ...
• 2,160
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 ...
• 156
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]//...
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 ...
1 vote
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 ...
• 121
1 vote
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 ...
• 322
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 ...
• 181
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),...
• 181
1 vote
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 ...
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 ...
• 233
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 ...
• 345
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 ...
• 149
1 vote
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 ...
• 113
1 vote
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 ...
1 vote
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 ...
• 111
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,...
• 149
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 ...
• 737
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 ...
• 181
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 ...
• 2,160
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 ...
• 2,160
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$ ...
• 149
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. ---------------------------------------------------------------------------------------------...
• 2,160
1 vote
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 ...
• 1,741
1 vote