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
77 votes
8 answers
25k 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,277
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
37 votes
7 answers
20k views

Why aren't zero-knowledge proofs used in practice for authentication?

I read on Wikipedia that zero-knowledge proofs are not used for authentication in practice. Instead (I think) the server is entrusted with seeing a password in plaintext form, which it should then add ...
wlad's user avatar
  • 1,239
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
33 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
  • 478
29 votes
4 answers
7k views

Why are zk-SNARKs possible, in layman's terms

zk-SNARK: Zero-Knowledge Succinct Non-interactive Argument of Knowledge From the Ethereum blog: One natural use case for the technology is in identity systems. For example, suppose that you want ...
bkoodaa's user avatar
  • 629
29 votes
1 answer
7k views

what is the difference between proofs and arguments of knowledge?

What is the difference between proofs and arguments of knowledge in the context of zero-knowledge? I have read this sentence in this ePrint: It is useful to distinguish between zero-knowledge ...
MH Samadani'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
25 votes
3 answers
6k 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's user avatar
  • 142k
24 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,376
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
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
18 votes
2 answers
5k 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
17 votes
1 answer
1k views

Salary Negotiation Problem

Imagine Alice is applying for a new job. Alice has an idea of the minimum salary that she is willing to accept—let's call this value A. Bob, the hiring manager for ...
Robert Quattlebaum's user avatar
16 votes
4 answers
5k views

Is there a cryptographic algorithm that can make a "lottery ticket"?

With public-key cryptography, I know Alice can "seal" a message that only Bob can open. But in that case, Alice knows the message that she is sealing. What if Alice wants to seal a random ...
mherzl's user avatar
  • 263
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
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
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,180
15 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
  • 151
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 ...
vnd's user avatar
  • 266
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
13 votes
1 answer
332 views

Proving multiple products "in the exponent"

I'm trying to come up with a small-sized (non-interactive) proof for a Diffie-Hellman-like statement. I'll start by giving an example. The prover has $g^a, g^b, g^c, g^{ac}, g^{ab}, g^{bc}, g^{abc}$. ...
Alin Tomescu's user avatar
  • 1,003
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,414
12 votes
3 answers
4k views

How to prove identity without revealing identity

Let us say Alice publishes a book under the name of Claire. The book becomes wildly popular and now Bob comes along, claiming to be Claire, to reap all the success. How does Alice prove that she wrote ...
Thomas Arildsen's user avatar
12 votes
5 answers
4k views

Can you explain what an NP statement is when they refer to it in Zero knowledge proofs?

When I read about zero knowledge proof, I keep encountering the term NP-statement. I am aware of complexity classes but I am a little unclear on how it ties up to NP-statement. I came across the ...
tatepairing's user avatar
12 votes
2 answers
2k views

How does the simulator of the special-honest verifier zero-knowledge property works?

I’m a bit confused about what the simulator of the special-honest verifier zero-knowledge property of a $\Sigma$-protocol is supposed/allowed to do and how to prove that it is indeed efficient (i.e. ...
LRM's user avatar
  • 1,376
11 votes
2 answers
664 views

Are interactive proofs more secure their non-interactive counterpart?

Given an interactive zk proof, if we use fiat-shamir to make it nizk proof, does the proof become less secure? Are there any new attack vectors that get introduced? Is there any reason to use the ...
WeCanBeFriends's user avatar
11 votes
1 answer
884 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's user avatar
  • 142k
11 votes
1 answer
298 views

Shadowed identity in cryptography

I was trying to implement zero knowledge protocol for authentication based on the paper "A Practical Zero-Knowledge Protocol Fitted to Security Microprocessor Minimizing Both Transmission and Memory". ...
user5507's user avatar
  • 1,923
11 votes
2 answers
4k views

How do zero knowledge protocol with vertex-3-coloring work?

I'm currently not sure if I understood how the zero knowledge protocol with vertex-3-coloring works. I'll describe what I think I've understood and I'll write my questions in bold. Zero-knowledge-...
Martin Thoma's user avatar
10 votes
6 answers
1k views

Mutual verification of shared secret

Is it possible to develop a scheme where two parties, unsure if they have the same secret, can verify that the other does or does not share the same secret, without one party being able to cheat and ...
codebeard's user avatar
  • 306
10 votes
2 answers
1k views

Zero-knowledge proof system which is not proof of knowledge?

I have learned that a zero-knowledge (ZK) proof system can be constructed by making use of the three-color problem. In this particular case, the proof system also happens to be proof of knowledge (POK)...
dkaeae's user avatar
  • 540
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
10 votes
2 answers
1k views

Why Victor must not know which tunnel Peggy chooses?

In the classic description of Zero Knowledge Proof of Knowledge, Victor must wait outside the entrance to the cave while Peggy goes to the fork and choose a side. It's only once Peggy has entered a ...
Yolanda Ruiz's user avatar
10 votes
1 answer
1k views

Why invent new hash functions for zero-knowledge proofs?

Recently, new hash functions were invented. Their primary purpose is serving the needs of zero-knowledge proof systems. I'm talking about Poseidon-256, Starkad-256, etc. See the paper. What is the ...
Paul Miller's user avatar
10 votes
4 answers
1k views

Zero-knowledge signature verification

Can you think of any solution to this problem? suppose we have three parties, A, B and C: A has some data signed by C, a small part of which (not the signature) it wants to hide from B. A wants to ...
Alvaro S.'s user avatar
  • 109
10 votes
1 answer
970 views

Is this a safe way to prove the knowledge of an ECDSA Signature?

I think that I've found a good solution to prove the knowledge of an ECDSA signature without revealing it. In short terms it consists in generating an ECDSA signature using the point $R$ as generator, ...
Jan Moritz's user avatar
10 votes
1 answer
1k views

What's the difference among Vector Commitment, Zero-knowledge Set, Zero-knowledge Accumulator, and Zero-knowledge Elementary Database?

Vector commitment allows one to commit to an ordered sequence of $q$ value ($m_1,\cdots,m_q$) in such a way that one can later open the commitment at specific positions (e.g., prove that $m_i$ is the $...
Qiang Wang's user avatar
10 votes
1 answer
461 views

Contradiction to the Sequential Self-Composability of Black-Box Zero-Knowledge?

In short: it is well-known that black-box zero-knowledge protocols are sequentially self-composable. However, Goldreich and Krawczyk [GK90] present a protocol which is proven to be zero-knowledge (in ...
Xiao Liang's user avatar
9 votes
2 answers
2k views

Converting to rank one constraint system (R1CS)

I was reading Vitalik Buterin's post$^\color{magenta}{\star}$ on ZK-snarks and I need some clarification on some points. Since there aren't that many posts and articles on the subject, I had no choice ...
Hesaam's user avatar
  • 115
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
1 answer
4k views

What is the link, if any, between Zero Knowledge Proof (ZKP) and Homomorphic encryption?

What is the link/relation, if any, between Zero Knowledge Proof (ZKP) and Homomorphic encryption?
Nathan Aw's user avatar
  • 2,277
9 votes
3 answers
2k views

Re-encrypting a message and proving that the message has not changed

Is there a method that allows for re-encryption of a message in a way that allows observers who only have access to the two cipher texts to prove that the plain text message is the same in each? More ...
zakum1's user avatar
  • 193
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
1 answer
2k views

Simulation Based Proof: What Can / Can not Simulator Do?

I have seen some examples in "Foundation of cryptography" and "Efficient two party computation", in which simulator can do some things that in the real world model the parties cannot do, for instance: ...
user13676's user avatar
  • 835
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.5k
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
9 votes
2 answers
3k views

Can I prove set membership and uniqueness without revealing the element?

Assuming a publicly known set $\Psi$ with $N$ unique elements. I have a set $\Sigma=\{\sigma_1,\sigma_2,...,\sigma_m\}$ where $m\leqslant N$. I would like to publicly prove that all the elements in $...
Deiwin's user avatar
  • 141
9 votes
4 answers
2k views

Schnorr protocol: how does malicious verifier win?

My question is about the challenge space size in Schnorr protocol. To be precise, I feel I've read all the Internet (twice) and I still don't understand why is it bad to allow challenge space to be ...
Alex Garkusha's user avatar
9 votes
1 answer
5k 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?
WeCanBeFriends's user avatar

1
2 3 4 5
22