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
25 votes
3 answers
5k views

Proving knowledge of a preimage of a hash without disclosing it?

We consider a public hash function $H$, assumed collision-resistant and preimage-resistant (for both first and second preimage), similar in construction to SHA-1 or SHA-256. Alice discloses a value $h$...
fgrieu - mod election time's user avatar
32 votes
1 answer
8k views

Is a hash a zero-knowledge proof?

I’m trying to wrap my head around zero knowledge proofs, but I’m having trouble understanding it. In my current understanding, zero-knowledge proofs prove to the recipient that the sender has a ...
vrwim's user avatar
  • 468
19 votes
3 answers
5k views

Is Using Digital Signatures to prove identity a zero knowledge proof?

Suppose Alice publishes a book with a public key in it, and later wants to prove that she wrote the book. She could sign challenge messages with her private key, and others could verify those signed ...
Scott Driscoll's user avatar
5 votes
1 answer
2k views

Zero knowledge proof for sign of message value

I am using ElGamal encryption to encrypt an integer message $m$ as, $E[m]$ = ($g^x$, $g^m.h^x$) Can I write a zero-knowledge proof to prove to a verifier that $m > 0$ ? I can create the bit ...
btan's user avatar
  • 153
15 votes
3 answers
8k views

Perfect zero knowledge for the Schnorr protocol?

Can somebody explain (or point to a reference) why the Schnorr protocol cannot be proved zero knowledge?
Panagiotis Grontas's user avatar
4 votes
1 answer
1k views

Proof of correctness of a homomorphic ElGamal sum

Let's suppose we are using the exponential ElGamal as a public-key encryption scheme, so that we encrypt $g^m$ instead of $m$, for some generator $g$. Let $x$ be the private key, and $h=g^x$ be the ...
LRM's user avatar
  • 1,356
2 votes
1 answer
894 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 ...
Shigeyuki Azuchi's user avatar
27 votes
1 answer
8k views

Zero knowledge proof protocol example?

Alice is color blind. She never knows if her gloves are matched. Her brother Bob always teases her saying her gloves are mismatched and she should go change them. Alice wants to know if Bob ...
user10956's user avatar
  • 271
23 votes
4 answers
4k views

When would one prefer a proof of knowledge instead of a zero-knowledge proof?

I've just realized I find it hard to distinguish between these two terms (proof of knowledge, and zero-knowledge proof), specially where only the latter seems to be used in many cryptographic ...
LRM's user avatar
  • 1,356
15 votes
4 answers
9k views

Proof of non-membership on a Merkle tree?

Assume a user $U$ and a server $S$. $U$ uploads its data and wants later to perform an authenticity check. It also sends a Merkle tree to the server. Let’s say we would like $U$ to ask for a specific ...
curious's user avatar
  • 6,150
13 votes
3 answers
3k views

Can we prove possession of an AES-256 key without showing it?

Imagine this situation: Alice has an AES256GCM key $K$, a plaintext $X$, and $Y$ which is the ciphertext of $X$ encrypted by $K$ Bob has $X$ and $Y$ Alice and Bob can communicate with each other Bob ...
tock203's user avatar
  • 345
10 votes
1 answer
2k views

How realistic is a dictionary attack on a secure remote password protocol (SRP) verifier?

I'm deploying a secure remote password protocol implementation and I'm wondering what the consequences are when the client generated verifier gets leaked to an attacker. I've read Thomas Wu's paper ...
Grant BlahaErath's user avatar
9 votes
3 answers
1k views

Practical consequences of a honest-verifier zero-knowledge of the Schnorr protocol

Schnorr protocol is known to be honest-verifier zero-knowledge and not perfectly zero-knowledge. What are the practical consequences of this fact? Does it mean a dishonest verifier can do something ...
omnomnom's user avatar
  • 491
9 votes
2 answers
3k views

Zero-knowledge proof of a product

I have non-negative integers $x,y,z$. I'm going to give you commitments $C(x),C(y),C(z)$ to them. Then, I would like to prove in zero knowledge that $xy=z$. I can choose the commitment scheme to ...
D.W.'s user avatar
  • 36.4k
7 votes
4 answers
1k views

Is there a public key semantically secure cryptosystem for which one can prove in zero knowledge the equivalence of two plaintexts?

If Alice encrypts two messages $a$ and $b$, such that $x=E(a)$, $y=E(b)$. Can Alice prove (without revealing $a$, $b$ or the private key) that $a = b$? Obviously the proof must not be too long and it ...
SDL's user avatar
  • 1,867
7 votes
2 answers
2k views

zk-SNARKs vs. Zk-STARKs vs. Bulletproofs: definitions

I have become quite familiar with Bulletproofs the last few months. Bulletproofs is the name given to a zero-knowledge proof system for arithmetic circuits, by Benedikt Bünz et al. It is a specific ...
Ruben De Smet's user avatar
7 votes
1 answer
2k views

What is difference between Zero Knowledge proof and Zero Knowledge Proof of Knowledge?

In a zero knowledge proof, a prover interactively proves to a verifier that an NP statement is true. If the language is an NP complete language and if the prover runs in poly time, the only way a ...
satya's user avatar
  • 1,404
5 votes
2 answers
1k views

How to verify a number encrypted with an unknown key

Alice and Bob are going to follow the protocol below. Are there any crypto-constructions to help Bob verify the correctness of the answer he gets?: Alice encrypts a set of numbers using some ...
Eugen's user avatar
  • 219
4 votes
2 answers
1k views

Why is a common reference string needed in zero knowledge proofs?

Can we have a non-trivial language without a CRS? Why?
WeCanBeFriends's user avatar
4 votes
1 answer
2k 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 ...
jeldzinski's user avatar
2 votes
2 answers
849 views

Finding out the greater number under zero-knowledge conditions?

Is it possible to construct a zero knowledge proof that one encrypted number is larger (or not) than another encrypted number without releasing the values of either numbers?
B T's user avatar
  • 194
1 vote
2 answers
531 views

Using two elliptic curves to do a range proof

Suppose Alice holds a secret value $a$ to which she has publicly committed to using two elliptic curves of distinct order. The curves are $g$ and $g'$ of orders $q$ and $q'$ (with $q < q'$) and ...
irakliy's user avatar
  • 969
51 votes
1 answer
20k views

What are SNARKs?

What does it mean and what is it used for, I have been hearing this term a lot lately. From the context I've heard it talked about it seems to be connected with zero knowledge?
wi1's user avatar
  • 613
35 votes
4 answers
11k views

What is a Non-Interactive Zero Knowledge Proof?

I understand the concept of a Zero Knowledge Proof thanks to the easy to understand analogy of Alibaba's cave. However, this seems to require interaction between the verifier and the other party. I ...
BBedit's user avatar
  • 481
18 votes
2 answers
4k views

Simulation-based proofs and universal composability proofs

I recently read Ran Canetti's famous UC paper but I'm still trying to wrap my head around the concepts. I think this answer has me confused a bit, particularly where it says The stand-alone ...
Luke's user avatar
  • 307
16 votes
2 answers
5k views

What are zk-STARK's?

The zk-STARK is a proof zero-knowledge proof system that, in contrast to the zk-SNARK, no longer relies on a trusted setup where the "toxic waste" parameters are initialized. What are, in layman's ...
CRYPTONEWBIE's user avatar
14 votes
2 answers
3k views

What is a "rewinding argument"?

I've been reading a bit about cryptographic protocols and I keep seeing the phrase "rewinding argument". I've been unable to find a good source that would explain what is meant by this. It seems like ...
Jaska's user avatar
  • 141
12 votes
3 answers
2k views

Examples of protocols that are insecure when run concurrently

I was reading Canetti00 Universally Composable security paper. The first page of introduction says that there are some MPC protocols and Zero knowledge protocols that are insecure under concurrent ...
satya's user avatar
  • 1,404
11 votes
1 answer
856 views

Minimizing exchanges for ZK proof of a message with given SHA-256

Consider the problem of proving knowledge of a message $m$ which has a certain public SHA-256 hash $h$, without disclosing $m$ or usable information about it, while minimizing the information exchange ...
fgrieu - mod election time's user avatar
9 votes
1 answer
1k views

Why does SRP-6a use k = H(N, g) instead of the k = 3 in SRP-6?

I've been reading up on the Secure Remote Pasword protocol (SRP). There are a couple different versions of the protocol (the original published version being designated SRP-3, with two subsequent ...
Robert I. Jr.'s user avatar
9 votes
3 answers
2k views

Proving the possession of signature in zero-knowledge

Does anybody know an efficient mechanism to prove the possession of a digital signature (e.g. RSA) on a certain attribute (message) in zero-knowledge? That is, without revealing the actual signature (...
OnTarget's user avatar
  • 453
8 votes
2 answers
2k views

Proof that lottery does not know outcome of draw

Could a variable participant lottery system cryptographically prove that they have zero knowledge of the outcome of a draw? Participants do not choose numbers in this lottery and winning numbers are ...
Thomas Tank Engine's user avatar
7 votes
2 answers
1k views

ZKP: Prove that >18 while hiding age

I am relatively new to cryptography, but I've been programming for a while. Here's a story that sets well the problem I'm trying to solve: Alice has a digital passport that's signed with her ...
deb's user avatar
  • 245
7 votes
1 answer
2k views

Did digital signatures come from Zero Knowledge Proofs?

I am reading the Real-World Cryptography book and in the chapter on signatures it says: The best way to understand how signatures work in cryptography is to understand where they come from. For this ...
Finlay Weber's user avatar
7 votes
1 answer
3k views

Why is the Pedersen commitment perfectly hiding?

I learned today about the Pedersen commitment scheme. A quick reminder (I know there are some variants of this scheme, so I will present the one I learned about): Public parameters - 2 primes $p,q$...
noamgot's user avatar
  • 287
5 votes
1 answer
830 views

Schnorr protocol - Proof or argument?

Is Schnorr's protocol for proving knowledge for a discrete logarithm, truly an interactive proof or is it an interactive argument? If we let P to be unbounded, after she generates the commitment $t$ ...
Andreas G.'s user avatar
5 votes
1 answer
1k views

Security of zero knowledge proof protocols

When designing a protocol based on zero knowledge proofs, be it based on the discrete log problem, or on a Hamiltonian cycle in a graph, or something else, I assume there are security considerations, ...
Ruben De Smet's user avatar
4 votes
2 answers
777 views

Prove I know a value $v$ in a Pedersen Commitment without revealing it

Given a Pedersen Commitment: $P = aG + vH$ Where $G$ and $H$ are points in some group. $a$ is a blinding value/mask and $v$ is the value I wish to commit to. Is there a way to prove I know $v$ ...
WeCanBeFriends's user avatar
3 votes
2 answers
499 views

Commutative homomorphic encryption for zero-knowledge transfers

I am trying to design a scheme that would allow the following: Alice has a number $a$ which she wants to keep secret Bob has a number $b$ which he wants to keep secret Alice can "transfer" a number ...
irakliy's user avatar
  • 969
3 votes
2 answers
589 views

Zero knowledge RSA public key

Suppose Bob has $k>1$ RSA public keys $(e_i, n_i)$ without any knowledge of their corresponding private keys. Alice also has all the public keys, but also has a private key for only one of them, ...
DeLorean88's user avatar
3 votes
3 answers
451 views

Zero-knowledge transfer of value protocol inspired by EC El Gamal

This is a follow up on the question I asked here. I designed a scheme that allows the following: Alice has a value $a$ which she wants to keep secret Bob has a value $b$ which he wants to keep secret ...
irakliy's user avatar
  • 969
2 votes
1 answer
1k views

Is it possible to create a zero-knowledge proof that a number is more than zero, and less than x?

Note: This might be similar to this question. I'm thinking about a hypothetical cryptocurrency where the blockchain doesn't store any transactions. The balance of an address would be stored by the ...
ndbroadbent's user avatar
2 votes
1 answer
2k views

zero-knowledge proof of disjunctive statements (OR proofs)

I know there are standard ways to prove disjunctive statements about discrete logs, e.g. OR proof. But are there similar approaches for other class of language? For example, how can one go about ...
qweruiop's user avatar
  • 326
2 votes
1 answer
324 views

Problem with Fiat-shamir on poly-round interactive protocol?

I have read in many places that Fiat Shamir technique is used to convert constant round interactive protocols to non-interactive arguments. What would be the problem in applying Fiat Shamir to poly-...
satya's user avatar
  • 1,404
2 votes
3 answers
332 views

Is there an oblivious decryption scheme?

Alice has $K$; Bob has $E(K, m)$; Is there such a scheme that enables Alice decrypts $E(K, m)$ without knowing $m$, and Bob gets $m$ ?
Jan Leo's user avatar
  • 915
1 vote
0 answers
81 views

Information sharing using interactive zero-knowledge system

I am trying to build a system that would allow information sharing in a kind of zero-knowledge way. Here is the set up: Let's say there is a trusted third party that has Alice's sensitive info M (e.g....
irakliy's user avatar
  • 969
0 votes
1 answer
152 views

Can we use non-adaptive zero-knowledge proof in group signatures

Group Signature schemes are used to provide anonymity of the signers. During signature generation, signers provide a NIZK proof to prove that they are certified group members. Verifiers check whether ...
preethi's user avatar
  • 889
0 votes
1 answer
340 views

How to compute a challenge c using Fiat Shamir?

I have a prover and verifier. They are engaged in a zero-knowledge proof protocol. A verifier sends a challenge $c$ to the prover so he can compute a proof using the value $c$. How to use Fiat Shamir ...
Mohamed's user avatar
  • 205
77 votes
8 answers
24k views

How do I explain zero knowledge proof to my 7 year old cousin? [duplicate]

How do I explain zero knowledge proof to my 7 year old cousin?
Nathan Aw's user avatar
  • 2,267
21 votes
2 answers
5k views

What is a “witness” in zero knowledge proof?

I've seen the term "witness" tossed around when talking about knowledge extractors, but I have no idea what it means. I can't find a definition. What is a “witness” in zero knowledge proof?
Zygro's user avatar
  • 319