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 ...
- 1,474
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, ...
- 18.9k
43
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 ...
- 18.9k
36
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 ...
26
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 ...
- 12.4k
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 ...
- 8,072
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 ...
- 4,672
19
votes
Accepted
Simulation-based proofs and universal composability proofs
What does this mean, exactly?
The purpose of the environment is to model "everything else happening in the universe" besides the protocol execution. In the UC model, the adversary is allowed to talk ...
- 11.7k
17
votes
Simulation based proofs: Simple examples
I have written a tutorial on how to write simulation-based proofs. I think that it should be helpful.
- 27.5k
17
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 ...
- 38.4k
16
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". ...
- 27.5k
14
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 ...
- 744
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. ...
- 18.9k
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 ...
- 18.9k
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 ...
- 18.9k
13
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$ ...
- 143k
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 ...
- 304
13
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 ...
- 18.9k
13
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 ...
- 18.9k
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 “...
- 21.2k
12
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-...
- 403
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 ...
- 27.5k
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 "...
- 121
11
votes
Accepted
How does the simulator of the special-honest verifier zero-knowledge property works?
Even following your edits, there's still some confusion about honest verifier zero knowledge and plain-old (i.e., "possibly malicious verifier") zero knowledge, which is a much stronger property.
...
- 5,773
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 ...
- 11.7k
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 ...
- 18.9k
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 ...
- 27.5k
10
votes
Accepted
Simulation Based Proof: What Can / Can not Simulator Do?
There is quite a bit of confusion in your question. First, differentiate between the real and ideal models. The adversary in the ideal model sends the adversary's input and gets its output (and can ...
- 27.5k
10
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 ...
- 18.9k
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 ...
- 45.7k
Only top scored, non community-wiki answers of a minimum length are eligible