# Tag Info

## Hot answers tagged zero-knowledge-proofs

8

Yes. Such proofs are possible for El Gamal. It involves a zero knowledge proof of equality of a discrete log, together with the homomorphic property of El Gamal encryption. Recall that given $E(a)$ and $E(b)$, anyone can form $E(a/b)$ using the homomorphic property of El Gamal. Suppose $E(a/b)=(r,s)=(g^k,h^k a/b)$ (where $g$ is the generator and $h$ is ...

6

Verifiable to whom? Someone else with the correct answer? Then you may be able to get away with a salted bcrypt hash; e.g., you can easily say make a cryptographically strong one-way hash of an answer: >>> import bcrypt #using py-bcrypt python module >>> hashed_answer = bcrypt.hashpw('[secret answer to problem 283]', ...

5

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

5

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

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

4

Protocols for selecting uninfluenced random numbers typically fall into two camps: random beacons and coin-tossing protocols. A random beacon is a source of randomness that is agreed by everyone to be unpredictable. For example, you can funnel a large amount of financial data into a small random number. While you cannot prove you didn't know what the ...

4

The security goal behind SRP is that an attacker that could either pretend to be a client (and attempt to log into a server that knows the key), pretend to be a server (and allow clients that know the key to attempt to log in), or actively monitor (and modify) the communications between a valid client and a valid server, would learn nothing from an exchange, ...

4

Well, if fake-Alice guesses the challenge exponent $e$ in step 1, then she can guess the value of $v^{-e}$. That means she can pick an arbitrary value to stand in for $r+se$, compute $g^{r+se}v^{-e}$, and send that as her commitment in step 1. Then, assuming Bob sends the guessed exponent in step 1, fake-Alice sends the value $r+se$ that she picked above. ...

4

If Alice guesses $e$ then she chooses a random value $x$ and computes $h = g^x v^{-e}$, a value which she sends to Bob at step 1. At step 3, Alice sends $x$. When Bob does step 4, he recomputes $g^x v^{-e}$ and finds $h$, and he is happy. However, Alice does not know $s$. The "commitment" at step 1 is a way for Alice to say: "I know a $r$ corresponding to ...

4

Suppose that we have Eve, that knows what $e$ is going to be, and does not need to know the prover's private key $a$, just the public one $v$. She then sends $g^k \cdot v^{-e}$ as her first "move", where she can choose her own $k$ (you can modify the $k$ in different plays to make it all look nice and random...). The verifier sends $e$ as expected, of ...

4

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 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 ... 3 The original 1986 Fiat-Shamir paper can be found here. The subsequent Feige-Fiat-Shamir 1988 paper can be found here, and contains the answer (Section 3): The$S_j$(which are witnesses to the quadratic residuosity character of the$I_j$) are effectively hidden by the difficulty of extracting square roots$\bmod n$, and thus A can establish his ... 3 In the other answers, you'll find how to simulate a proof if you know$e$. This answer is meant to provide some "color commentary" on the other answers. It is a companion piece. Notation In step 1, Alice sends$g^r$. Call this value$a=g^r$. In step 3, Alice sends$r+se$. Call this value$b=r+se$. In step 1-3, one value is sent in each step: {$a,e,b$}. ... 3 You probably don't need to re-encrypt using the Paillier crypto system. 1) Alice encrypts$c_1=g^{m_1} r_1^n$und$c_2=g^{m_2} r_2^n$and computes$r_3=r_1 \cdot r_2$and$m_3=m_1+m_2$, then sends$c_1$,$c_2$,$m_3$and$r_3$to Bob 2) Bob computes$c_3=c_1 \cdot c_2=g^{m_3} r_3^n$- If the homomorphically computed sum matches the re-encryption Bob will ... 3 First let's develop a zero knowledge interactive proof. The verifier doesn't know$p,q$as otherwise he could just take the roots. Let$a$be the putative residue, and have$P$know a square root$t$. So P will take a random number$r$and send$r^2$to V. V will send a bit, either$0$or$1$. If$0$P sends$r$to V. If$1$P sends$rt$to V. This is ... 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

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

2

Actually, it is not necessary for the prover to show that "exactly half" of elements with Jacobi symbols being +1 are, in fact, QR. Instead, here are some hints: Assuming that n is not of that form (and also n is not of the form $n = p^a$, which is easy test for), the probability that a random element with Jacobi symbol +1 is a QR is at most $q$ (homework ...

2

I believe that you are talking about one specific version of EKE, which is one of several known Password authenticated key agreement methods (which is the general category of methods that do a key agreement with the property that someone listening into the exchange can't learn anything, and an attacker that poses as one of the two sides can learn no more ...

2

The U-Prove Technology Overview V1.1 shows that this can be done. The issuer knows who the individual is but can't correlate that with verifier or prover use. Upon setup the issuer can have extra attributes available that upon request of authorization from the prover the verifier can have access to. The verifier could use such an attribute and only ...

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

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

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

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

1

Yes. This can be solved through standard methods. Alice can prove she decrypted the ciphertext correctly by revealing the decrypted message and the random coins that would be used in encryption to obtain this ciphertext from this message. Suppose we have a ciphertext $c$, and Alice decrypts it to obtain the message $m$. It follows that $c = g^m r^n \bmod ... 1 Rewinding is used in all sorts of interactive protocols, but it's perhaps easiest to understand it for a zero-knowledge property. In proving zero-knowledge, we consider a cheating verifier interacting with an honest prover. The prover knows something that the verifier doesn't (say, the factorization of an RSA modulus), and we worry that by cheating, the ... 1 Let us briefly recall the Paillier encryption. Let$k_{pub} = (N = PQ, g)$be a public key, where$N$is the RSA modulus. The secret key is$\lambda = \mathrm{lcm}(P-1,Q-1)$(or$P,Q$). The encryption of$p \in \mathbb{Z}_N$with randomness$r \in \mathbb{Z}_N^*$is$C = g^p r^N \bmod{N^2}$. You can verify$\mathbb{Z}_{N^2}^* \simeq \mathbb{Z}_N \times ...

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