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
3 votes
1 answer
104 views

Rigorous Proof on Malicious Zero-Knowledge Property of Schnorr Protocol

Let us recall the Schnorr Protocol, following Chris Peikert's excellent Notes on the Theory of Cryptography. Protocol. Let $G=\langle g \rangle$ be a cyclic group of order $q$. We consider an ...
Chris's user avatar
  • 236
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. ...
untreated_paramediensis_karnik's user avatar
4 votes
1 answer
130 views

In Zero Knowledge Proofs (ZKP) why does the simulator and extractor get the power to rewind "time" and not some other superpower?

Why was the simulator/extractor specifically given the power to rewind "time" instead of a different super power? Was it defined in the first ZKP paper that the simulator and extractor would ...
CLox's user avatar
  • 151
2 votes
1 answer
232 views

GKR Protocol - is it one Sum-Check per layer or is it one Sum-Check per gate?

I am reading about GKR protocol from Justin Thaler's book - Proofs, Arguments & Zero Knowledge On Page 59, In the first message, $P$ tells $V$ the (claimed) output(s) of the circuit. The protocol ...
user93353's user avatar
  • 2,200
0 votes
0 answers
34 views

Interactive Zero-Knowledge Proof for the Multiplication Gate

Refer to an interesting article (link) on Medium on the subject matter. To understand more about pRandomValue and vRandomValue. The article mentioned, "pRandomValue, on the other hand, is used to ...
user60588's user avatar
  • 307
1 vote
0 answers
49 views

In zero-knowledge proof, can the selection of challenge r be non-uniform?

I recently started learning zero-knowledge proofs. I found that in many zero-knowledge arguments, the verifier is required to randomly select a challenge $r\in\mathbb{Z}_q$ and send it to the prover. ...
Wing Sky's user avatar
1 vote
1 answer
110 views

How does the verification step operations using FRI polynomial commitments in zk-STARKs?

I have been going through the lectures in ZKP MOOC here youtube series. I am trying to understand the zk-STARKs discussed in video ZKP MOOC Lecture 8: FRI-based Polynomial Commitments and Fiat-Shamir. ...
INDUKURI MANI VARMA 21911012's user avatar
1 vote
1 answer
189 views

How to write zk-snark arithmetic circuits

Paper: "Dispute-free Scalable Open Vote Network using zk-SNARKs" by Muhammad ElSheikh Available at: https://arxiv.org/pdf/2203.03363.pdf In this paper, the author has mentioned some pre-...
user60588's user avatar
  • 307
1 vote
0 answers
40 views

Is it possible to verify and prove the decryption of an FHE cyphertext without the verifier knowing the key with zkProof?

Suppose Bob encrypts a plaintext($p$) with an FHE scheme and a key($k$), then sends the $c$ to Alice. Alice wants to know the plaintext but can't trust that Bob won't send a different string. Can Bob ...
Vasily Sobolev's user avatar
2 votes
2 answers
87 views

Impact of security of schnorr's identification verifier when reducing the challenge space

I have been going through some old lecture notes of mine and found this interesting question. Assuming we reduce the challenge space for the verifier from $\mathbb ℤ_q$ to $\mathbb ℤ_{\log(𝑞)}$, does ...
user16100351's user avatar
0 votes
0 answers
25 views

Zero Knowledge Protocol for 3Coloring: Formal Proof

I am learning zero knowledge protocols, and studied the GMW protocol for 3-Coloring (https://www.wisdom.weizmann.ac.il/~oded/X/gmw1j.pdf). A similar proof is also presented in Oded Goldreich's ...
user31245's user avatar
1 vote
1 answer
155 views

Clarification on Modular Equivalence in Generalized Sumcheck in RZ21

I'm studying generalized sumcheck in RZ21 P.10 and have come across a modular equivalence that I'm trying to understand. The specific step that's unclear to me is the following equivalence: $$ \left(\...
Paul Yu's user avatar
  • 156
2 votes
1 answer
42 views

How is $\lambda_j(0) = N^{-1}$ for Lagrange polynomials in the Baloo paper's generalized sumcheck?

I'm reading inner product from generalized sumcheck in baloo paper (P.13), I'm confused with $\lambda_j(0) = N^{-1}$. Can anyone shed some light? Here's excerpt from the paper The intuition is that ...
Paul Yu's user avatar
  • 156
0 votes
0 answers
31 views

How do I instantiate ZK-STARKs using Polynomial Commitments?

In my exploration of zero-knowledge proofs, I have encountered various perspectives on the operational disparities among zk-SNARKs, zk-STARKs, and Bulletproofs, as documented in different blogs and ...
INDUKURI MANI VARMA 21911012's user avatar
1 vote
0 answers
47 views

Server parameters for Differential Zero Knowledge?

I'm working to use Differential Zero Knowledge proof on client local data before sharing with server. May I know which parameters need to be established at server side as to verify that the client is ...
Genie's user avatar
  • 83
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 ...
Makubu's user avatar
  • 21
1 vote
1 answer
60 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$, $r$ a factor of $n$, $k(r)$ for the embedding degree of $E(F)$ with respect to $r$. Then why the full $r$-torsion group contains $r^2$...
l4rmbr's user avatar
  • 111
2 votes
0 answers
54 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)>\...
ohmygoddess's user avatar
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, ...
Cocodile's user avatar
1 vote
0 answers
83 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 ...
HughJass24's user avatar
0 votes
0 answers
42 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 ...
Prady Tej's user avatar
2 votes
1 answer
161 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 ...
LightTunnelEnd's user avatar
1 vote
0 answers
28 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?
Kanchan Bisht's user avatar
2 votes
0 answers
52 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 ...
pintor's user avatar
  • 558
0 votes
0 answers
48 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 ...
user109993's user avatar
1 vote
0 answers
32 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 ...
user109993's user avatar
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? ...
user109993's user avatar
2 votes
1 answer
139 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 (...
user109993's user avatar
1 vote
0 answers
106 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,...
Bernardo Rodrigues's user avatar
1 vote
2 answers
102 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 ...
Justice Almanzar's user avatar
0 votes
0 answers
25 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 ...
Walker's user avatar
  • 61
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 ...
Jordan's user avatar
  • 111
1 vote
0 answers
104 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 ...
limeeattack's user avatar
1 vote
1 answer
102 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:...
vxek's user avatar
  • 477
3 votes
3 answers
311 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 ...
Gareth Ma's user avatar
  • 365
0 votes
0 answers
47 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 ...
Lev's user avatar
  • 468
2 votes
1 answer
126 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, ...
smoking_big_ole_doinks's user avatar
1 vote
1 answer
170 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 ...
Lev's user avatar
  • 468
1 vote
0 answers
40 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 ...
user109993's user avatar
1 vote
0 answers
46 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 ...
user93353's user avatar
  • 2,200
1 vote
0 answers
40 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 ...
drydrydesert's user avatar
2 votes
0 answers
154 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 ...
Seed Barret's user avatar
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 ...
TheStrangeQuark's user avatar
1 vote
1 answer
99 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 ...
884d88baaa's user avatar
1 vote
1 answer
87 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....
user93353's user avatar
  • 2,200
2 votes
1 answer
187 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$ ...
user93353's user avatar
  • 2,200
0 votes
0 answers
44 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 ...
joakimb's user avatar
  • 243
1 vote
1 answer
154 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)...
Seed Barret's user avatar
3 votes
1 answer
198 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 ...
Atonal's user avatar
  • 155
1 vote
1 answer
65 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 ...
user7308228's user avatar

1
2
3 4 5
22