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
1 answer
72 views

Σ-protocol that proves an even number was committed using Pedersen commitment scheme

I need to design a Σ-protocol ZKP using Pedersen commitment scheme that proves knowledge of a, y such that statement A = h^y * g^a only holds for even y (y=2x). Of course, the protocol needs to be ...
user avatar
  • 11
-3 votes
0 answers
132 views

Give ordering as A<B<C<D by comparing MiMC,Poseidon, Pedersen and SHA256 in terms of Gas cost, capacity, proof generation efficiency, proof size [closed]

I need to compare the 4 hashing techniques-MiMC,Poseidon, Pedersen and SHA256 in four aspects gas cost, capacity, proof generation efficiency and proof size. Efficieny can be compared based on proven ...
user avatar
  • 1
1 vote
1 answer
43 views

Range proof for elgamal ciphertext

Alice has an ElGamal public key $y=g^x$. Bob encrypts a value $g^b$ based on Alice's Elgamal public key and he ends up with a ciphertext $(g^by^r, g^r)$. Can Bob prove that the value $b$ is in some ...
user avatar
1 vote
0 answers
40 views

Proving stategies for computational properties

As far as I understand, a property is computational if it holds in a computationally-bounded context, so for ANY computationally-bounded involved entity (even if an unbounded one could discover the ...
user avatar
  • 448
0 votes
0 answers
14 views

Bounded honest-verifier simulator and unbounded prover

I have a honest-verifier zero knowledge simulator $M$. The conversation between prover and verifier has the usual $(a, b, z)$ form. How can the bounded model $M$ generate $a$ and $z$ is the prover is ...
user avatar
1 vote
0 answers
60 views

Can I prove that from a set of ciphertexts one is encrypting $g^0$ and the others are encrypting $g^b$ where $b$ is a negative value?

Consider for example this set of encrypted values under the Elgamal keys $y_0$,$y_1$,$y_2$: $$ Enc_{y0}(g^0),Enc_{y1}(g^{-20}),Enc_{y2}(g^{-10}) $$ Can I prove that one value is $g^0$ and the others ...
user avatar
0 votes
0 answers
48 views

Can a circuit in a zk-SNARK be reversed-engineered?

The definition of zk-SNARK involves not leaking any information from the prover-verifier interaction, but what about leaking information from the circuit itself? e.g., could there be a circuit to ...
user avatar
  • 1
0 votes
0 answers
10 views

What do we mean by "Efficient Computing" of a Span Program (SP)?

I'm reading "Quadratic Span Programs and Succinct NIZKs without PCPs" and I'm having trouble understanding the "Efficiency" of a span program. I can see that a span program cannot ...
user avatar
1 vote
0 answers
19 views

Should proving key be kept as a secret in NIZK?

Hi I am quite new to NIZK. I know a trusted party (Generator) generates proving key and verifying key and then distributes them to Prover and Verifier. Apparently, the verifying key can be seen as ...
user avatar
  • 31
0 votes
1 answer
50 views

Zero Knowledge proof of correct ElGamal encryption

Suppose for $sk = x$, $pk = g^x$ we encrypt message $m$ with ElGamal encryption as $(g^r,m\cdot pk^r)$. My goal is to prove that I performed the encryption correctly, i.e. that the same $r$ is used ...
user avatar
  • 164
2 votes
2 answers
155 views

Understanding the "rewinding argument"

I read through related questions on this SE, but I still do not understand why we can use the rewinding argument. Specifically, rewinding seems like a really strong superpower to me, and I don't ...
user avatar
  • 23
2 votes
1 answer
58 views

Authenticated Diffie-Hellman with no proofs that each one keys are the right keys. Is it possible?

Let's suppose that Bob has only Alice's IP and no more information about Alice's key, nor the digest of Alice's key. They exchange keys and need proof that the received keys are the same keys that ...
user avatar
0 votes
0 answers
71 views

How to prove knowledge of a secret and allow the receiver to deduplicate it?

Consider the following scenario: We have two agents, A and B. B needs to prove that they know a secret to A, without sharing the actual secret. e.g.: A needs a way to de-duplicate the secrets they ...
user avatar
0 votes
0 answers
25 views

How to Run the Public Key Protocol for a Zero-Knowledge Proof of Identity?

In the paper Zero-Knowledge Proofs of Identity (by Feige, Fiat, and Shamir) a ZK protocol is described that leverages quadratic residues. Section 3 describes an "Efficient Identification Scheme,&...
user avatar
1 vote
0 answers
26 views

Proving the range of a blinded value in a Pedersen commitment in zero knowledge

A prover has the following value: $$C = (h^ag^x)^b$$ and he needs to prove in zero knowledge to a verifier that $x < t$, for some public threshold $t$. The verifier knows $h$, $g$, $C$, and $t$. ...
user avatar
  • 11
1 vote
1 answer
65 views

Why are zk-STARK quantum secure?

I have a rough idea of how STARK work, but I want to know which part makes them quantum secure. Is it because when the prover generates the proof they use the random number from the Merkle root, which ...
user avatar
1 vote
1 answer
56 views

Create an or-proof for a given list of elements with public input

Let $g\in G$ and $h\in H$ be two group generators. Given a list L of m group elements, where $L=(L_1,...,L_m)$, a prover wants to convince a public verifier (namely, a verifier who only has public ...
user avatar
  • 11
0 votes
0 answers
18 views

Data encryption or Blockchain in data sharing between *multiple* sources?

imagine several parties that own data, and some of them need to use data of other parties, but have only limited access rights to it. An example: Party #1 (pharmacy store) needs confirmation from ...
user avatar
3 votes
1 answer
91 views

How to do a non-membership proof for a committed value?

Assume that the verifier is given three commitments $C_i=g^{m_i}h^{r_i}, i=1,2,3$. Now a prover knowing $m_i, r_i, i=1,2,3$ wants to prove $m_3\neq m_1\wedge m_3\neq m_2$. Specifically, the relation ...
user avatar
  • 707
4 votes
2 answers
119 views

Relation between Knowledge extractor and soundness in ZKPoK

Reading Why Zk-SNARKs are Argument of Knowledge if a Knowledge Extractor exists? I feel confused by OP first statement: From what I know, proving the existance of a Knowledge Extractor implies ...
user avatar
  • 448
0 votes
1 answer
60 views

Chaum–Pedersen Protocol explanation for dummies. What I'm doing wrong?

The screenshot from a book with Chaum–Pedersen Protocol description is below. I'm trying to implement it for my own. And I don't get math here. My assumptions: Discrete Logarythm functions: The dot ...
user avatar
2 votes
1 answer
205 views

Chaum-Pedersen Protocol

I'm junior software developer and I need to implement a very simple authentication system based on Chaum-Pedersen ZKP Protocol. I know nothing about cryptography and I ask you to help me understand ...
user avatar
1 vote
0 answers
51 views

Detailed Proof of Knowledge for Discrete Log

I'm having difficulty finding a detailed proof for one of the most basic protocols in cryptography, that is the Schnorr protocol, or the sigma protocol for proving knowledge of a discrete log. Most ...
user avatar
1 vote
0 answers
33 views

IS there a way to do zk proof on string?

For example: "I am a very secret person". I'd like to show someone that this string includes 'secret' without revealing the rest of the string. Is there anyway?
user avatar
  • 111
1 vote
0 answers
48 views

What is required to verify a zk-SNARK?

I am trying to verify a zk-SNARK from a solidity contract offline, in Rust. This is the verifying contract that checks the proof in the solidity side. And this is the transaction that carries the ...
user avatar
0 votes
1 answer
52 views

Zero knowledge proof of integer factorization

If I have public element $W=K^r$, and $K=v^x$ should be kept secret where $v$ is a generator in $\mathbb G$, is there a way to produce a zero knowledge proof on x and r such that $W=v^{x \cdot r}$ ...
user avatar
  • 1
2 votes
1 answer
63 views

Zero Knowledge Proof: groth16. Can prover key be public?

Here is quote from gnark documenation. Note that careful consideration must be given to this step in production environment. groth16.Setup uses some randomness to precompute the Proving and Verifying ...
user avatar
  • 123
2 votes
1 answer
158 views

What's the meaning of without loss of generality in cryptography? [closed]

What's the meaning of without loss of generality in the cryptography (Zero Knowledge Proof)? Without loss of generality, suppose we want to check if a 1 = a 2 . In the following description, j ∈ { 1, ...
user avatar
  • 205
2 votes
0 answers
88 views

How to extract witness from a non-interactive lattice-based proof?

I'm trying to figure out how to construct an extractor for a non-interactive lattice-based proof. Specifically, I'm curious about the Fiat-Shamir transform applied to a five-move interactive protocol. ...
user avatar
  • 390
2 votes
1 answer
54 views

What's the meaning of verifier is "ppt" ? and why we need verifier is ppt in Interactive Proof?

I have been studying Zero Knowledge Proof. I found the Definition of Interactive Proof says that Verifier is ppt. And I only found in PP (Complexity) Wikipedia says that ppt: Turing machines that are ...
user avatar
  • 205
0 votes
0 answers
37 views

The simulation sound extractable NIZK

I was recently reading the paper Hawk: The Blockchain Model of Cryptography and Privacy-Preserving Smart Contracts. To prove the security, the authors assume that the NIZK used in the protocol is ...
user avatar
0 votes
1 answer
59 views

zkSNARKs: Doing the setup for the Single Variable Operand Polynomial

I am reading this explanation of zkSnarks written by Maksym Petkus - http://www.petkus.info/papers/WhyAndHowZkSnarkWorks.pdf My question is about Section 4.6.1 Setup construct the respective operand ...
user avatar
  • 1,678
2 votes
1 answer
121 views

Range proof for elements in Vector Pedersen commitment

If I construct a vector pedersen commitment $c = a_1G_1 + a_2G_2 + ... + a_nG_n$ with an arbitrary scalar vector $(a_1, a_2, ..., a_n)$ and group elements $(G_1, G_2, ..., G_n)$, is it possible to ...
user avatar
14 votes
5 answers
2k views

Cryptographically safe lookup of value in a set

I'm looking for an elegant solution to the might-seem-trivial problem of looking up for specific value in a known set of values without disclosing what value we look for. Let me describe it in a ...
user avatar
  • 266
3 votes
2 answers
117 views

What exactly does "Extension of a polynomial" mean?

This from the manuscript of a book on Zero Knowledge Proofs - https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf 3.5 Low Degree and Multilinear Extensions Let $\mathbb F$ be any finite ...
user avatar
  • 1,678
2 votes
0 answers
24 views

Probabilistic Verifiers for NIZK in the CRS model

Can we assume without loss of generality that the verifier for non-interactive zero-knowledge proofs in the common reference string model is deterministic, or does random randomization add extra power?...
user avatar
  • 21
0 votes
0 answers
39 views

'NIZK arguments for quadratic arithmetic programs' of '[Groth16] On the Size of Pairing-based Non-interactive Arguments'

I wonder about the CRS of NIZK argument. I think [A]$_1$, [B]$_2$, [C]$_1$ is calculated using CRS. Instead of calculating A, B, C first and then calculating [A]$_1$, [C]$_1$, [B]$_2$. May I know if ...
user avatar
1 vote
0 answers
85 views

Is it possible to prove possession of AES-128 key?

My question is kind of related to this topic: Can we prove possession of an AES-256 key without showing it? But I couldn't figure out how to apply it to my problem. Description: Lets say I have a ...
user avatar
  • 11
1 vote
1 answer
49 views

Proof of knowledge of constant discrete log in the bilinear setting

Consider a pairing $\mathbb{e}: \mathbb{G}_1\times \mathbb{G}_2\longrightarrow \mathbb{G}_T$ with generators $g_1$, $g_2$ for $\mathbb{G}_1$, $\mathbb{G}_2$ respectively. The groups $\mathbb{G}_1$, $\...
user avatar
1 vote
1 answer
131 views

zkSnarks: Ensuring that a variable has a single value across all the operations it is used in

I am reading this explanation of zkSnarks written by Maksym Petkus - http://www.petkus.info/papers/WhyAndHowZkSnarkWorks.pdf In section 4.5, the pdf explains how to represent the following operations $...
user avatar
  • 1,678
1 vote
1 answer
74 views

zkSnarks: Why does the target polynomial $t(s)$ need to be kept a secret if it's known to both prover & verifier?

I am reading this explanation of zkSnark written by Maksym Petkus - http://www.petkus.info/papers/WhyAndHowZkSnarkWorks.pdf The example used here is that there is a polynomial of degree 3 which the ...
user avatar
  • 1,678
1 vote
1 answer
59 views

Proving to a 3rd party an email received in a@domain2.com was truly sent from a@domain1.com

Example: I send an email from address@domain1.com to address@domain2.com Using only the email I received in address@domain2.com, I'd like to prove to a 3rd party that I also own address@domain1.com ...
user avatar
1 vote
1 answer
64 views

zkSNARKS: If we are already using Homomorphic Encryption/Hiding, why is the shift by $\delta$ required for Zero Knowledge?

I am reading this explanation of zkSnark written by Maksym Petkus - http://www.petkus.info/papers/WhyAndHowZkSnarkWorks.pdf From Section 3.5 Because verifier can extract knowledge about the unknown ...
user avatar
  • 1,678
1 vote
1 answer
70 views

zkSNARKS: What prevents the prover from chosing a different polynomial than the one he is expected to know

I am reading this explanation of zkSnark written by Maksym Petkus - http://www.petkus.info/papers/WhyAndHowZkSnarkWorks.pdf Here the Prover knows a polynomial of degree 3, 2 of the solutions of the ...
user avatar
  • 1,678
1 vote
1 answer
82 views

How can I prove the preimage of a hash that contains a number is bigger than x?

So I want to create a zero-knowledge proving system for numbers (think loans and bank accounts, I want to prove my paycheck is more than x dollars per month). I was thinking about using a zero-...
user avatar
  • 398
1 vote
1 answer
84 views

Prover cost of QAP based zkSnark

In CGPR (link to paper) Section 3.5, it is mentioned that the cost of prover is $O(|C| \log(|C|))$, given the size of the circuit is $|C|$. It looks to me that the polynomial degree in the resulting ...
user avatar
  • 113
1 vote
1 answer
32 views

zkSNARKS - unable to understand the usage of polynomial to verify some condition

From Vitalik Buterin's Blogpost - An approximate introduction to how zk-SNARKs are possible From the sub-topic "Comparing a polynomial to itself", I understood till here In other words, any ...
user avatar
  • 1,678
2 votes
1 answer
60 views

How to guarantee that a ZKP was generated honestly?

The following extracts were taken from the Zero-Knowledge Proof page on Wikipedia: In cryptography, a zero-knowledge proof or zero-knowledge protocol is a method by which one party (the prover) can ...
user avatar
0 votes
0 answers
75 views

how do you prove you are not a bot with a zero knowledge proof?

I communicate with another person online, I know he is a person because sometimes he also writes real messages but at random timeframes whenever I send him a message he only responds with a dot maybe ...
user avatar
  • 131
2 votes
1 answer
79 views

Commit the output of verifiable random functions

The problem setting is as follows. Suppose there exists a public input $x$ and the prover evaluates $y \gets VRF_{sk}(x)$, but the prover does not wish to reveal the output $y$. My question is would ...
user avatar

1
2 3 4 5
17