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
0 votes
0 answers
10 views

Format of the circom output files - is it documented?

In the circom documentation, I found file formats for their input files, but I cannot find documentation format for their json exported output file. I ran the following circom commands till the end of ...
0 votes
0 answers
20 views

The zero-knowledge properties of lattice-based zero-knowledge proofs

I've been reading papers on lattice-based zero-knowledge proofs recently, and I have some questions about the proof of zero-knowledge properties of schemes. Why is Stern type proven to achieve ...
2 votes
1 answer
108 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),...
5 votes
1 answer
67 views

Why does extractability not contradict zero-knowledge?

I was introduced to the QR-protocol that shows that a number y is a quadratic residue modulo x through an interactive protocol. The protocol is perfect zero-knowledge but it also proves that the ...
0 votes
0 answers
36 views

Has anyone used Arkworks with Spartan?

I'm trying to use Spartan to produce and verify zkSNARKS. I want to use Arkworks (https://github.com/arkworks-rs) to create custom R1CS instances, but Arkworks does not readily interface with Spartan. ...
0 votes
1 answer
117 views

Proving anonymous credential presentation

In a CL-based or CKS-based anonymous credential system, how can a verifier $V$ prove that a credential holder $H$ has presented it a credential that has been issued by an issuer $I$ without ...
2 votes
1 answer
193 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 ...
2 votes
0 answers
44 views

3-Coloring Zero-Knowledge Proof: rational verifier?

I'm studying the application of Zero-Knowledge Proofs (ZKP) to graph 3-colorability. I haven't fully understood the need for randomness in the verifier's choice of the edge to challenge the prover ...
1 vote
0 answers
37 views

Given powers of tau ; the veryfying and the proving key, how can I find the point [f] resulting from the trusted setup in Groth16?

For each circuits, Groth16 requires to compute a point $f$ such as $f=s×G$. While revealing the scalar $s$ used for computing $f$ would allow to produce fake proofs, $f$ can be exposed to the public. ...
2 votes
2 answers
94 views

Groth16 - Since the Circuit Specific Trusted Setup requires knowledge of the QAP, how does it not leak knowledge?

In the Groth16 paper, Page 14, the terms below have to computed as part of the circuit specific trusted setup $$ \left ( \frac{\beta u_i(x)+ \alpha v_i(x)+ w_i(x)}{\gamma} ^{\ell}_{ i=0}, \frac{\beta ...
2 votes
4 answers
303 views

Is it possible to verify and relay an encryption key with a trusted but transparent third party?

I'm wondering if it would be possible to implement this functionality with a trusted but transparent third party (maybe an Ethereum smart contract?): Bob has an encryption key. Alice has the ...
0 votes
1 answer
45 views

Are polynomial hash functions over prime order fields ZK-friendly?

"Traditional" hash functions such as SHA2/SHA3 are not considered ZK-friendly because their translation in the native prime fields of the ZK-proof system leads to a large number of ...
2 votes
1 answer
249 views

How to understand this detail of a zkSNARK-protocol?

As a beginner in cryptography and zk-SNARKs, I am currently working through the paper "Why and How zk-SNARK Works". There, I don't understand the last section at the bottom of page 15: ...
4 votes
1 answer
518 views

Can I prove in zero knowledge that the public key corresponding to a secret that I committed is in the Accumulator?

I have a set of users in my system, each having a private/public keypair of a digital signature scheme. I also have an accumulator in my system, where all the public keys of the users are accumulated. ...
2 votes
1 answer
65 views

Efficient NOT in set proof?

I am looking for a solution for a very specific problem, I have one, but I am not statisfied with it and it feels there must be a much more efficient way to do this. I have a hashed value of 256 bits. ...
0 votes
1 answer
56 views

What techniques other than zero-knowledge proofs can prove consistency in one-to-many scenarios?

Assuming that there is a sender and multiple receivers, the sender will send the signature $\sigma$ of a certain message $m$ to all receivers, and the signatures $\sigma$ received by these receivers ...
2 votes
1 answer
81 views

Languages $L$ that have perfect zero-knowledge that do not have any $AM$ proof system that is perfect or zero-knowledge on $L$

In the GMR[85] paper, a conjecture is made in section 3.7: There exist languages $L$ that have perfect or statistical zero-knowledge proof systems, but do not have any Arthur-Merlin proof system that ...
1 vote
1 answer
79 views

Why do many ZKSnarks divide the Inputs into Public & Private Parts?

Many zkSNARKS (for e.g. Groth16) divide the Inputs into 2 parts - the public parts & the private parts. I understand how some of the stuff in the solution vector is known to both prover & ...
3 votes
1 answer
76 views

Why are the expressions divided by 2 random elements $\gamma$ & $\delta$ in Groth16?

In Groth16 Page 14 The prover does $C = \frac {\sum_{i = l+1}^m a_i ( \beta u_i(x) + \alpha v_i(x) + w_i(x)) + h(x)t(x)}{\delta} + As + r\beta − rs\delta$ And the verifier $A \cdot B = \alpha \cdot \...
4 votes
1 answer
78 views

Why is the first coefficient set to 1 in both GGPR13 & Groth16 SNARKS?

From GGPR13 Section 7.1, Page 42 ($v_0(x) +\sum_{k=1}^m a_k \cdot v_k(x)) \cdot (w_0(x) +\sum_{k=1}^m a_k \cdot w_k(x)) - (y_0(x) +\sum_{k=1}^m a_k \cdot y_k(x))$ If you notice, the term $a_k$ is ...
0 votes
2 answers
132 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? ...
1 vote
1 answer
54 views

Linear commitments for groups beyond $\mathbb{Z}_p$

I need a construction for the following: Given a group $\mathbb{G}$ of order $p$, enable a party to commit to a vector $(x_1,\ldots,x_N)\in\mathbb{G}^n$ in a way that, in a later phase, the party can ...
0 votes
0 answers
34 views

Zero Knowledge Proof of a Time Machine

I'm a software engineer trying to wrap my brain around Zero Knowledge Proofs just out of curiosity. I came up with the following puzzle to test my understanding... but was unable to solve it. Your ...
1 vote
1 answer
61 views

Zero-Knowledge in PLONK paper in prover round 3. Shouldn't the degree be less than n?

From the PLONK paper. On page 29, in the prover algorithm round 3, we divide the quotient polynomial into three polynomials of degree < n. But when we add the blinding terms we add $X^n$. The ...
1 vote
0 answers
40 views

A zero-knowledge proof for ElGamal signature

If I want to add zero-knowledge proof to the ElGamal signature, is it reasonable to write that? $$ \pi \gets \operatorname{NIZK.Prove}\bigl(u=((r,s),y,m),w=(x,k)\bigr) $$ $$ R=\{u,w:g^{H(m)}=y^rr^s \...
0 votes
0 answers
33 views

Zero-Knowledge Proof of a number being generated "randomly" (similar to a dice roll)

If party1 asks other parties to give a random number, for simplicity, say in a range from 1 to 6 (like in a dice). Is it possible for party1 to ensure that the number received is in a given range and ...
1 vote
0 answers
18 views

Mental Poker: Can the shuffle of the deck be done Publicaly by a single player at the start of the game

Ref: Mental Poker Revisited by Barnett and Smart. I am looking at mental poker problem. Generally, the shuffling process is done by a single player who starts the game and not by all players. But, in ...
0 votes
0 answers
36 views

Special PoK verifying signature of a hidden message

Alice has a hidden message $g^{a \alpha}=(g^a)^\alpha$ where $g^a$ is the message, and a signature $s$ on $g^a$ from Charlie. She sends both $g^{a \alpha}$ and $s$ to Bob. She later wants to prove to ...
1 vote
1 answer
230 views

Can interactive zero-knowledge proof systems be implemented using secure two-party computation?

I am defining multi-party computation using the real-ideal paradigm (see A Pragmatic Introduction to Secure Multi-Party Computation). That is, for any successful attack on an MPC protocol in the real ...
1 vote
3 answers
205 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 ...
9 votes
2 answers
6k views

What is a rank-1 constraint system?

Why not rank-2 constraint system or rank-3 constraint system? How do rank-1 constraint systems link to circuits?
0 votes
2 answers
246 views

Does Schnorr identification protocol using commitment scheme?

In schnorr identification protocol, a prover needs to choose a random,let's say $r$ at the beginning, then commit to this randomness as $g^r\bmod p$. When we say "commit", does it really mean we are ...
0 votes
0 answers
38 views

Can ring signatures be considered as non interactive set membership proofs?

Can ring signatures be considered as non interactive set membership proofs? For example, if the message msg is set to null, can the ring signature scheme proposed by Rivest et al. be regarded as a non ...
1 vote
1 answer
57 views

Winner and individual vote counts in online voting in DRE-i and DRE-ip

I have seen few well-known related papers on online voting : DRE-i, DRE-ip and this one. They have explained most of the process such as vote casting and vote tallying. But I did not find when and ...
1 vote
0 answers
38 views

Mask-Shuffle in Mental Poker Revisited from Barnett and Smart

I am going through the paper "Mental Poker Revisited" by Barnett and Smart. I understood Section 5 in which the author explains Chaum-Pedersen (CP) protocol and how it is used in methods ...
0 votes
0 answers
29 views

In groth16, how restricting public Inputs to the prime field instead of the snark scalar field can be used?

Recently such an overflow was fixed in snarkjs but given the small difference between the 2 and that it was restricted to the prime field anyway, how could this be exploited ?
0 votes
2 answers
141 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 vote
2 answers
597 views

Proof of knowledge and replay attacks

I was reading the ZK proof of knowledge of Schnorr and fiat shamir transformation, and I figured out that replay attacks are possible. Why these protocols don't take into account this attack? That ...
0 votes
1 answer
74 views

ZK is not preserved under parallel composition! - Witness Indistinguishability

Referring to an old but very nice paper on Witness Indistinguishability and Witness Hiding (link). On page 4, in theorem 3.2, the author explained it in three points, but I have few queries. In point ...
2 votes
1 answer
132 views

Is it safe to "sign" a message with such a zk proof

I am building an application in which I need to sign a message without revealing my entire identity. To do so, I just compute a zk proof with the following purpose: prove I own the secret key sk ...
2 votes
0 answers
49 views

Succinct proof of evaluation of known polynomial

Consider the zeroes polynomial $$ zeroes_n(X) = \prod_{0\leq i< n} (X-i) . $$ Fix a large prime $p$, and fix some $n$ that is less than $p$ but which may still be very large (e.g. $p\approx 2^{256}...
3 votes
1 answer
123 views

Zero knowledge proof of a linear expression in the exponent

Alice sends to Bob a value $B$ in $\mathbb{G}$ a group of high order. There are distinct elements $h_1$ and $h_2$ of high order of $\mathbb{G}$, and Alice wants to prove to Bob that she knows some ...
0 votes
1 answer
47 views

Zero knowlede proof of linear relations

Suppose a prover publishes two perfectly hiding commitments for $s_1,s_2$, i.e. two Pedersen commitments $C_1=g^{s_1}h^{r_1}$ and $C_2=g^{s_2}h^{r_2}$ such that $s_1,s_2,r_1,r_2$ are secret field ...
0 votes
0 answers
64 views

Is the PLONK paper incorrect? [duplicate]

I'm having some confuses while implementing the PLONK by following the instruction in the Plonk paper. Could someone please help me with it? In step 6th of the "Verifier preprocessed input" ...
1 vote
0 answers
46 views

Simulating physical envelops: Will commitments work in this case?

I want to simulate following physical activity in cryptography. Person X has written integers 1, 2, ..., 10 in seperate paper slips. He needs to distribute these slips to 10 people without knowing ...
1 vote
1 answer
270 views

Zero knowledge proof applied to a chess position

I know next to nothing about cryptography. From what I have understood, anything that is provable can be done so using a zero knowledge proof (the result seems to be known from the 1980's or so, by S. ...
2 votes
1 answer
146 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 ...
2 votes
1 answer
61 views

Equality check with Pedersen commitments

Does the Pedersen commitment scheme allow for checking whether two commitments are made - say by different people - for the same value?
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....
1 vote
0 answers
62 views

A problem involving Commitments

Suppose there is a set $P=\{p_1, p_2, ..,p_l\}$ of stock buyers who can make commitments to a share $s_i$ in a set $S=\{s_1,s_2,...,s_m\}$ of shares for an amount $a_i$ in a set $A=\{a_1,a_2,...,a_n\}$...

1
2 3 4 5
22