# Tag Info

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

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

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

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

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

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

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

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

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

1

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

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

1

Given the definition of a zero-knowledge proof, it must satisfy three properties: Completeness: if the statement is true, the honest verifier (that is, one following the protocol properly) will be convinced of this fact by an honest prover. Soundness: if the statement is false, no cheating prover can convince the honest verifier that it is true, ...

1

You have to look at the response from the perspective of the verifier. This specific construction allows him/her to verify the $P$'s knowledge of $x$: If $P$ could answer two different request $c_1,c_2$ in step 2) then we would have $g^{s_1}=ty^{c_1}$ and $g^{s_2}=ty^{c_2}$. Dividing one equation by the other we get $g^{s_1-s_2}=y^{c_1-c_2}$. Let ...

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 Uprove/anonymous credentials in general seems a bit heavy handed for that. You could accomplish it with simple Chaum style e-cash. The issuer does a blind signature on a serial number. To vote, you reveal the serial number and signature. Its anonymous and doesn't allow duplicate voting. In fact, since u-prove credentials are single show, you could cause ... 1 Reading the original paper, I figure out the question. This voting scheme employed the well-known undeniable signature scheme, proposed by Chaum and Van Antwerpen in 1989 (or Chaum 1990 or Chaum and Van Antwerpen 1991). KeyGen: The RA is a signer and has a public key$X = g^x$and a secret key$x$Sign: For a message$m \in \mathbb{G} = \mathbb{Z}_p$, the ... 1 Unfortunately, you are probably not going to be able to fill in the missing details, unless you have a great deal of crypto experience (which it sounds like you don't have). You could start by reading about zero-knowledge proofs. There's a lot of information on that subject available. You will need to know it before you can progress. It sounds like you ... 1 Revealing$r$would then allow the verifier to prove to someone else (another verifier) that$c$encodes$i$. The verifier could also prove other things knowing$r$to a different verifier (any other proof using a paillier ciphertext, the corresponding plaintext, and the random value$r\$). With the ZKP, the verifier cannot prove anything to anyone else ...

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