# Tag Info

11

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

5

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

5

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

5

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

5

Let me attack if you (the verifier) always select $b = 1$ as a random challenge. The zero-knowledge proof for QR. Let us recall the zero-knowledge proof for QR. The common inputs are $y$ and $x$ and the prover possesses a witness $w$ which satisfies $w^2 \equiv y \pmod{x}$. The prover generates a randomness $r \gets \mathbb{Z}_x$ and sends $a = r^2 ... 4 Private Set Intersection How about a private set intersection protocol? The banks input is a set of all of their account numbers, the user's input is their account number (a single member set). The output could be given to the user, or the bank, or both, depending on your needs. You would need a way to protect against guessing account numbers. For ... 4 Let$\#G$denote the number of elements in the group. In your particular case,$\#G = \varphi{}(n)$(and even$\#G = n-1$if$n$is prime). Let$\xleftarrow{\$}$ denote a uniformly random sampling from a finite set of elements. Furthermore, $\mathbb{Z}_m$ denotes the set of non-negative integers smaller than $m$ and $\stackrel{?}{=}$ denotes a equality test ...

3

The description of this "kid zero knowledge" example follows the strucure of how interactive proofs that are zero-knowledge usually work: The prover sends a commitment (walks into one of the two sides) The verifier challenges the prover (tosses the coin to decide which side the prover should walk out) The prover gives a response (walks out the side the ...

3

The problem is one of notation for modular arithmetic, at the point of the question reading if y^2 equals (x * v^e) % n then.. Likely the textbook is about if $y^2\equiv x\cdot v^e\pmod n$ then.. By definition of $a\equiv b\pmod n$, that holds if and only if $n$ divides $a-b$ (or equivalently: $|b-a|$ is a multiple of $n$). In the question, 437 ...

3

In very simplified terms, a NI-ZK proof works in 2 stages: First, you run the protocol with a simulator (who is just a verifier, but the random choices are done differently), and then you can give the transcript of the protocol to anyone and convince them that the proof is real. The most important ways to achieve this are: In the random oracle model ...

3

Alice can prove that the decryption of $C$ is $M$. This can be done using zero knowledge proofs. Simple example: Suppose $C = (x,w)$ is an ElGamal encryption of $M$ under public key $y$, that is $(x,w) = (g^r, y^r M)$ for some $r$. Suppose that the decryption key is $a$, that is, $y=g^a$. Then we know that $M = wx^{-a}$, or $x^a = w/M$. That is, the ...

3

The question is not very clear about exactly what you want to prove and what is publicly known, but here's my answer, based on my best guess at what you mean: Each party should publish $(R_1,S_1)$ and $(R_2,S_2)$. They should also publish $(R_3,S_3)$. Now anyone can verify that $(R_3,S_3)$ is a correctly-formed encryption of the sum of the messages ...

3

As noted by Perseids in a comment to this answer, the formula $s = r + c + x$ would allow an adversary (who has completed the protocol once in the role as verifier with $P$ and already got one valid triplet $t_1,c_1,s_1$) to compute responses to any arbitrary challenge, simply using the formulas $t_2 = t_1$, $s_2 = s1 + c_2 - c_1$. Your other alternative $s ... 3 If they don't trust the server they sure shouldn't send any money. The "trusted" third party is used to solve the problem of participants who don't trust each other. So by definition, your problem can only be somewhat mitigated, not solved completely. I'm not sure what you mean by "provably fair". If the server can't prove he cannot cheat, it's not provably ... 2 Zero knowledge in general What are they good for? What is a typical scenario? This is an interesting question. One application is authentication: You can choose the secret yourself and not even the server will know it, and it will never be transmitted in any way. You just prove you know the secret again and again. However, in practice this is rarely ... 2 So a fundamental property of multi-party anonymous systems is you are only anonymous out of the number of honest participants in the system. If the Stasi control everyone else at the dinner table and know they didn't send the message, then they know you did no matter what protocol you use. In your case with this ring topology, because only your two ... 2 As nightcracker notes in the comments, the real problem in your bank scenario is that the account number is doing double duty as both an identification token and as an authentication token. The solution is equally simple: make the account number public and use it only for identification. Have Alice's bank issue her another number (let's call it a PIN) that ... 2 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 ... 2 The usual way to encode long random bitstrings, so that they can be easily memorized and/or entered by humans, is to break them into blocks of (typically) 10 to 12 bits and map each block to an entry in a fixed dictionary of common words. This approach is commonly used for secure passphrase generation, e.g. by Diceware, S/KEY and PGP. Assuming an 11-bit ... 2 Ok, here we are speaking of non-interactive zero-knowledge proof systems for some language$L\in NP$. We there have a pair$\sf (P,V)$of probabilistic polynomial time algorithms (called the prover and the verifier) where both have input$x\in L$and$\sf P$additionally holds a secret witness$w$for membership of$x$in$L$and wants to convince a ... 2 SRP doesn't require very much memory, has a low transmission cost (4 packets), and its CPU usage isn't very high (less than 1 second on a low-end 32-bit CPU, but higher on something like an 8-bit CPU). http://en.wikipedia.org/wiki/Secure_Remote_Password_protocol 2 A homomorphic cryptosystem has some operation$*$on ciphertexts that correspond to some other operation$\circ$on plaintexts, that is $$\mathcal{D}(c_1 * c_2) = \mathcal{D}(c_1) \circ \mathcal{D}(c_2).$$ Typically, the ciphertexts you get by applying$*$look like ciphertexts that are produced by the encryption algorithm. For Damgård-Jurik,$*$is ... 2 Below is one possibility, but for a large set of values not a really efficient one as the work and the size is linear in the number of values. Say we are working in a cyclic multiplicative group$G$of prime order$p$with generators$g$and$h$(such that the discrete logarithm between$g$and$h$is unknown to the users) and I assume that the values on ... 2 The original question was: Alice knows:$a,b$and$x$such that$a^{(x\cdot x)} = b$Bob knows:$a,b$and DrLecter referenced this paper (fixed the link), which covers the question. Now, the question was changed to Alice knows:$b$and$x$such that$x^x=b$; Bob knows:$b$. The given structure was: ... multiplicative group$G$... 1 There are a couple of problems with this zero knowledge proof; it isn't explained very well it gives the verifier more information than it claims to Lets go through them in order: It isn't explained very well The problem is that the terminology it uses in the proof statement differs from the terminology they use in the protocol description; for ... 1 First, before I answer your questions: Money rewards are not forbidden, as far as I know, but that's not how it goes here. Feel free to check out the according question on crypto-meta. I think, there are few conceptual misunderstandings in your scenario. First, a signature scheme uses the private key (also called signing key) to sign messages, and it uses ... 1 Yes, this is doable. You can verify that$m=a \times b$, given El Gamal encryptions of$m,a,b$, since El Gamal is multiplicatively homomorphic. You can also prove that the El Gamal decryption of some ciphertext is in a given range (using a combination of Schnorr proofs). Putting those two together will give your first desired primitive. This requires you ... 1 My goal is to create a voting scheme that doesn't require a lot of crypto infrastructure ... I would like these anonymised ballots to be publicly accessible for verification. It sounds to me like you want a end-to-end voter verifiable voting system. Some of them do require a lot of crypto infrastructure, but it sounds like several others already ... 1 My guess would be that they have a proof that their scheme has the zero-knowledge property if the challenge comes from the set$\{0,1\}$, whereas the proof doesn't work if the challenge comes from the set$\{0,1,2,\dots,2^{160}-1\}\$ -- and they don't know how to construct an alternate proof to show the latter. If you want to understand why their proof ...

1

Collusion is a concern but unlikely in very large ad-hoc ring networks where each ring is a one-shot random walk of a suitably large and mostly trustworthy membership pool. Collision and congestion are problems though; read below. If the opponent(s) can determine where the message or the key to decipher the message came from, the poster is done for. ...

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