# Tag Info

93

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 which look same but one of them tastes like chocolate and the other one tastes like spinach. Your cousin claims that he can distinguish them just by looking at ...

69

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, numbered from 1 to 100. The riddle is the following: I hold a key which opens one of the locks. However, the keys are numbered as well: if I show you the key, ...

49

I assume you are familiar with $P$ and $NP$. Also, my knowledge of SNARKs is based mostly on the work of Parno et al., other work may differ in some fine details. So, a SNARK is a succinct non-interactive argument of knowledge. Leaving the "knowledge" part aside for the moment, let's look at "plain" succinct non-interactive arguments (called SNARGs in the ...

35

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 explaining. I heard this example during one of the guest lectures back in my grad school. I think it is simple enough since I've myself used it many times, ...

35

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 knowledge of some information without disclosing it, but something much, much more powerful: the goal is to prove that you know some information$^1$ without ...

29

This is a classical example. Here is the proof system… Bob gives two gloves to Alice so that she is holding one in each hand. Bob can see the gloves at this point, but Bob doesn't tell Alice which is which. Alice then puts both hands behind her back. Next, she either switches the gloves between her hands, or leaves them be, with probability $1/2$ each. ...

24

A non-interactive ZK proof is when you play with yourself. Or, more accurately, with an impartial version of yourself. In a normal ZK proof, the prover first issues a bunch of commitments, then the verifier issues challenges that the prover complies with; this proves anything only as long as the verifier is assumed to issue challenges normally without any ...

22

Answering the question in your title (and not addressing your proposed alternative which I don't quite understand) there is a zero knowledge proof of password protocol "SRP" which is fast and effective. SRP does not seem to have been given as wide publicity as it should get. Having implemented it, and being an advocate of its use, I don't really understand ...

20

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 often called "computationally sound proofs".

20

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 conclude that you somehow learned the entry code, because I do not know of any other way by which you could have entered my room without breaking the door or windows....

18

Formally, this is all very complicated, but informally: An interactive proof is a conversation between a prover and a verifier that ends with the verifier either accepting or rejecting. The interactive proof can be zero knowledge, in which case a cheating verifier does not learn anything new by talking to the honest prover. The interactive proof can be a ...

18

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 to the environment during the execution of the protocol. So UC security means "security no matter what else is going on in the world, even if other things are ...

17

I have written a tutorial on how to write simulation-based proofs. I think that it should be helpful.

17

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 Alice and Bob just run the protocol with their respective inputs A and B.

14

Schnorr can be proven zero knowledge when the challenge $e$ is restricted to a small set (typically $0$ and $1$). Recall that in the Schnorr protocol, the prover knows the logarithm $u$ of $y$ to base $g$. He chooses a random value $r$, computes $a = g^r$ and sends $a$ to the verifier. The verifier chooses a random challenge $e$ from some set and sends it ...

14

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. Given such a boolean circuit $C$ (that both parties can construct), Alice must prove that she knows an input $K$ to $C$ so that $C(K) = 1$. The task of proving ...

13

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". This can be meaningful for two reasons. Let's say that I want to prove to YOU that I wrote the book, but I don't want you to be able to convince anyone else ...

12

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$ (I was apparently wrong of course). Why isn't that correct? Because there are lots of different $r, s$ pairs that satisify the solution. In particular, for ...

11

SRP does DH key exchange with authentication, and has the capability to also authenticate the server as well (though usually the server is authenticated by keeping the verifier secret). If the key is generated strictly from a password and salt, with the salt stored on the server, you can do a dictionary attack on the verifier (e.g. if the server is ...

11

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 not journals. This isn't to say that journals don't have an important role; rather, you don't follow journals to see what research is being done - you follow ...

11

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 will follow the same pattern. (As will every "-" operation, "*" operation, and "/" operation) Example using '+' operation: ...

11

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 "Look inside") The goal of the reader is to find Wally, a specific character. Suppose Alice knows where Wally is in a specific picture, and she wants to prove ...

11

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 situations. The soundness of the protocol is not based on the Diffie-Hellman problem. This is probably the most important point to address. What does it mean for ...

11

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 want me to develop some specific aspect, you can ask in the comments. Most of what I will say will not be specific to proving knowledge of a SHA-256 preimage, but ...

10

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 also sometimes determine if the honest party gets output, depending on the model). We often call the ideal adversary a "simulator" since this is how we build the ...

10

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. Your description of HVZK is essentially correct, but with the following clarifications: A 3-move protocol between a prover P and a verifier V for a language $L$ ...

10

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 what solution is the most appropriate in a given situation. Therefore, to let you evaluate by yourself what might best suit your exact situation, I'll attempt at ...

10

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 graph, a witness would be such cycle. Given a cycle, one can efficiently check whether it is a valid Hamiltonian cycle, but finding such cycle is difficult. ...

10

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 proofs of knowledge. Even though it seems intuitively true, there is no known general reduction from "I can prove that this word belongs to this language" to "I ...

10

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 & 1 & 2 \end{array}$$ Let's say Alice has input from $\{L,R\}$ (she chooses a column) and Bob has input from $\{U,D\}$ (he chooses a row). A ...

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