Hot answers tagged zero-knowledge-proofs
7
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 ...
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
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 ...
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
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
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, ...
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
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 ...
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 ...
1
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 ...
1
I wanted to comment on PulpSpy's answer, but my comment turned out to be too large!
I have an intuitive understand why they does not stick to the idea of using Boolean circuits alone for all the proofs which I am writing it down here. I might be wrong and I would like to be cross examined on this.
There will be an issue with the boolean and arithmetic ...
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 ...
1
It seems, what you are looking for is a Non-Interactive Zero Knowledge Proof of Knowledge (NIZKPok) of a discrete logarithm.
The Schnorr identification scheme is an (interactive) ZKPoK and can be transformed in to a non interactive one (in the random oracle model) using the Fiat-Shamir transformation.
It works in any group, is perfectly sound and ...
1
I think your original idea could be tweaked slightly to avoid the problem Poncho pointed out.
Alice generates 3 files and a signature.
The message m1 (possibly including the recipient list).
a file m2, a list of true random numbers Ti (one per recipient).
a file m3, containing only a list of hashes -- for each recipient, Alice calculates a hash value, ...
1
Here is one way for a Receiver Ri to prove to Verifier V that it received some message m from Alice, and is therefore a member of a the set of people who directly or indirectly received that message m from Alice, without disclosing the message m or the identity of any other Receiver.
Alas, this assumes the receivers and the verifiers are trustworthy.
Alice ...
1
Here is one way for a Receiver Ri to prove to Verifier V that it received some message m from Alice,
and is therefore a member of a the set of people who directly received that message m from Alice,
without disclosing the message m or the identity of any other Receiver.
Alice and R7
Alice composes a message something like "To whom it may concern. If ...
1
How can I prove in zero knowldege that an ElGamal shuffle is correct for a special setting? [closed]
I don't understand the question (what is public? what is secret? what is the definition of all variables and functions?), but I can give you a pointer to literature that I strongly expect is highly relevant:
Take a look at mixnets. There's an enormous amount of research literature on the subject. It solves the following sort of problem (as well as ...
1
Yup, should be possible. Look at multiparty secure computation protocols.
In particular, you might want to look at secure protocols for private set intersection. $P_1$ and $P_2$ can use such a protocol to find the individuals that are in the intersection of a set known to $P_1$ and a set known to $P_2$. Then, they can let $S$ know whether there is any ...
1
You are in a twist here:
semantic security (equal to IND-CPA) can only be fulfilled by probabilistic encryption schemes.
You need a deterministic encryption scheme for your drop-out tolerance.
As it was pointed out previously, any homomorphic encryption allows you to proof in zero knowledge the equality of two ciphertexts:
known: $c_0 = ...
1
There's one important difference about SRP and EKE that wasn't clearly explained above :
SRP is an augmented password authenticated key exchange
EKE (at least the initial version that RFC 6124 uses) is not
This means that with EKE as described in RFC 6124 both the server and the client must know the password.
Whereas with SRP the server only knows a ...
Only top voted, non community-wiki answers of a minimum length are eligible
