# 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 ...

66

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, ...

45

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 ...

33

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, ...

33

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 ...

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....

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.

16

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 ...

15

If k is a constant, such as 3, it becomes possible to select a pair (N,g) such that the discrete log of k to the base g is known, which would enable the two-for-one guessing attack again.

15

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 ...

14

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

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

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 ...

13

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 ...

13

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".

12

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

I don't believe your protocol meets the standard definition of Zero Knowledge Proof, as a cheating verifier can learn more information about the secret than allowed. In particular, suppose we have a cheating verifier (server) that has a list of one million potential passwords. Then, he can run your protocol with a client that knows the password, run the ...

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 ...

10

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 ...

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

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 ...

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 ...

9

I'm not sure what I can add that wasn't covered in the talk. The approach is that Alice commits to the preimage and sends the commitment to Bob. The commitment has homomorphic properties, meaning it is possible to do computation on the value. For example, if Alice commits to $x$ and $y$, Bob may be able to compute a commitment to $z$ where $z=f(x,y)$ for ...

9

Here's what can happen if you don't do this verification: Suppose Alice, Bob and company generate their public key shares honestly, $h_2, h_3, ..., h_n$ Now, Snidely Whiplash (who is also a trustee) is the last to contribute his share, he selects a private key $x_{evil}$ and computes $h_{evil} = g^{x_{evil}}$. However, instead of sharing $h_{evil}$ as his ...

9

Your idea is exactly what is achieved in a recent paper: Blind Certificate Authorities. Liang Wang, Gilad Asharov, Rafael Pass, Thomas Ristenpart, abhi shelat. At IEEE S&P 2018. The server and client use secure multiparty computation to jointly make an SMTP+TLS connection to a mailserver, generating the appropriate encrypted packets to send an email ...

9

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 ...

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