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 ...
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 ...
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
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 ...
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 ...
1
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 ...
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
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 ...
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 = ...
Only top voted, non community-wiki answers of a minimum length are eligible
