Skip to main content
97 votes

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

I will use Bertie Bott's Every Flavour Beans from Harry Potter in my explanation. If your cousin has not read Harry Potter, you can refer to Jelly Beans instead. So let's assume there are two beans ...
VincBreaker's user avatar
  • 1,484
72 votes

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

There is a riddle that I was given a few years ago which, in my opinion, explains the concept quite well - and it can be easily understood by a 7 year old. Suppose we have, say, a hundred open locks, ...
Geoffroy Couteau's user avatar
45 votes
Accepted

Is a hash a zero-knowledge proof?

There are three issues in your proposal, which I'll go over one by one; I hope this will clarify the concept. The first issue is that the purpose of a zero-knowledge proof is not only to prove ...
Geoffroy Couteau's user avatar
35 votes

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

This question has been asked on Information Security StackExchange a couple of years back and I will bring you Rahil Arora's answer (the accepted one), because I think it does an excellent job at ...
27 votes
Accepted

what is the difference between proofs and arguments of knowledge?

Yes, you are right. In a proof, the soundness holds against a computationally unbounded prover and in an argument, the soundness only holds against a polynomially bounded prover. Arguments are thus ...
DrLecter's user avatar
  • 12.6k
21 votes

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

When you have eliminated the impossible, whatever remains, however improbable, must be the truth. (Sherlock Holmes) If I find you in my dorm room and the door and windows are intact, I can only ...
fkraiem's user avatar
  • 8,152
21 votes
Accepted

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

Bob picks an integer $n$ between 0 and 9 (inclusive), and a uniformly random 128-bit blinding factor $b$. Bob informs Alice of the hash commitment $c=H(n \mathbin\| b)$. $H()$ is a cryptographically ...
knaccc's user avatar
  • 4,740
18 votes
Accepted

Salary Negotiation Problem

Solutions to Yao's Millionaire's Problem should suffice for this computation. In that setup, there are two parties each with an input. The output reveals whose input is larger, and nothing else. So ...
mikeazo's user avatar
  • 38.7k
17 votes
Accepted

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

This is not zero knowledge. In particular, you give away information in the form of signatures on challenges. This is something that the verifier doesn't have and so it is something that is "learned". ...
Yehuda Lindell's user avatar
16 votes

What is a “witness” in zero knowledge proof?

A witness for an NP statement is a piece of information that allows you to efficiently verify that the statement is true. For example, if the statement is that there exists a Hamiltonian cycle in some ...
Christian Matt's user avatar
15 votes
Accepted

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

How do you define "having" or "knowing" the witness? This question, which is much less intuitive than it may seem, is the core reason behind the difference between proofs of language membership and ...
Geoffroy Couteau's user avatar
15 votes
Accepted

Could Diffie-Hellman protocol serve as a zero-knowledge proof of knowledge of discrete logarithm?

This is an interesting question. In fact, cryptographers have been using this exact protocol on many occasions, and there are two important reasons to prefer Schnorr over this protocol in most ...
Geoffroy Couteau's user avatar
14 votes
Accepted

Why is the Pedersen commitment perfectly hiding?

When I was asked if even an unbounded adversary can learn anything, I thought that such adversary can iteratively try possible values of $r,s$ until he finds such values that satisfy $C = g_1^s g_2^r$ ...
poncho's user avatar
  • 148k
14 votes
Accepted

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

Yes she can. She would do so by relying on a boolean circuit that takes $K$ as input, uses it to encrypt the plaintext $X$, compares it to $Y$, and outputs $1$ if and only if the comparison succeeds. ...
Geoffroy Couteau's user avatar
14 votes
Accepted

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

There are many. Homomorphic encryption implies ZK proofs for NP. This is simply because homomorphic encryption implies one-way functions, which imply ZKP for NP. Homomorphic encryption allows to ...
Geoffroy Couteau's user avatar
13 votes
Accepted

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

Yes, there are general zero-knowledge proofs for all statements in NP. This result dates back to a paper by Oded Goldreich, Silvio Micali and Avi Wigderson from 1986. The basic idea is to give a zero-...
real-or-random's user avatar
13 votes
Accepted

Zero knowledge proof for sign of message value

What you are looking for is called a range proof. There has been a vast body of research on the topic recently - so vast, in fact, that it can be quite hard to know what is the state of the art, and ...
Geoffroy Couteau's user avatar
13 votes
Accepted

Converting to rank one constraint system (R1CS)

what does he mean by saying " There is a standard way of converting a logic gate into a (a, b, c) triple depending on what the operation is " ? He means that every "+" operation ...
ninni21's user avatar
  • 304
13 votes

Cryptographically safe lookup of value in a set

You are describing the problem of 1 out of $n$ Oblivious transfer with $n=366$ if it is required that Alice receives no extraneous information. The methods of Kolesnikov et al in their paper “...
Daniel S's user avatar
  • 24.1k
12 votes
Accepted

The main differences between Sketch of Proof and Full proof

The answer to this question is not straightforward and has a lot to do with the "conference culture" of computer science. Unlike other fields, the main publication venues for CS are conferences and ...
Yehuda Lindell's user avatar
12 votes

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

Consider a "Where's Wally" (or "Where's Waldow?") book. This is a children's book in which every page displays a chaotic, very dense illustration of many persons and items. (See example here, click "...
Itamar K.'s user avatar
  • 121
11 votes
Accepted

What is the difference between honest verifier zero knowledge and zero knowledge?

The intuition behind Zero Knowledge is that the Verfifier should not learn something about the secret. That means, that the communication between the Prover and the Verifier ("Transcript") must not ...
Christine's user avatar
  • 353
11 votes
Accepted

Examples of protocols that are insecure when run concurrently

Consider the function $f : \{L,R\} \times \{ U,D \} \to \{0,1,2\}$ defined by the following table: $$ \begin{array}{c|cc} f & L & R \\ \hline U & 0 & 0 \\ D ...
Mikero's user avatar
  • 13.5k
11 votes
Accepted

Are interactive proofs more secure their non-interactive counterpart?

When turning an interactive ZK proof into a non-interactive zero-knowledge argument with the Fiat-Shamir transform, the following security issues must be taken into consideration: Even if the ...
Geoffroy Couteau's user avatar
11 votes
Accepted

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

To answer every part of this question in full details would require almost a book. Here, I’ll attempt to address all sub-questions and give a brief summary together with pointers each time. If you ...
Geoffroy Couteau's user avatar
11 votes
Accepted

Why Zero-Knowledge protocols are used for NP problems if IP is the class of interactive proof systems where they come from?

The reason is that essentially, the class of languages in $\mathcal IP$ that are not in $\mathcal NP$ cannot be proven with an efficient prover. Since we are typically interested in the cryptographic ...
Yehuda Lindell's user avatar
10 votes
Accepted

What is the difference between 'completeness' and 'soundness' in ZKP?

The two notions are not specific to ZK, so it is in fact better to try to understand it in the context of general proof systems. Soundness: the proof system is truthful, so whatever it proves, it is ...
AYun's user avatar
  • 849
10 votes
Accepted

ZKP: Prove that >18 while hiding age

AFAICT, no, she can't do that using just the information on her passport, as you describe it,* and treating the digital signature algorithm as a black box. However, if the government has foreseen this ...
Ilmari Karonen's user avatar
9 votes
Accepted

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

Take it back a step, and consider a more simple zero knowledge proof. A digital signature on an email can be thought of as a very specific, narrow example, of a zero knowledge proof. I (the 'prover')...
JesseM's user avatar
  • 462
9 votes
Accepted

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

There are certainly ZK proof systems which are not known to be POK, and for which no knowledge extractor is known. For example, take the Goldreich-Kahan 4-round ZK proof system. However, do we know of ...
Yehuda Lindell's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible