# How can I prove in zero knowldege that an ElGamal shuffle is correct for a special setting? [closed]

In a special ElGamal encryption scheme, every user has an ElGamal encryption key-pair using the same cyclic group $G$ and generator $g$.

The system has a special function :

$$\mathrm{ShuffleEncrypt}(m_1, m_2, h_1, h_2 ) = \text{RandomPermutationOf} ( \operatorname{Enc}( h_1,m_1) , \operatorname{Enc}( h_2, m_2) ) = ( a, b)$$

$m_1$ and $m_2$ are plaintexts.

So given two public keys $h_1$ and $h_2$ and two plaintexts the function encrypts them and shuffles the resulting ElGamal ciphertexts ($a$ and $b$).

I want to prove in zero knowledge that $\mathrm{ShuffleEncrypt}$ was correctly done:

• $m_1$, $m_2$ and the ElGamal randomization values must be kept hidden.
• The ZNP must prove that $m_1$ and $m_2$ were known to the party doing $\mathrm{ShuffleEncrypt}$.

The verifier knows $h_1$, $h_2$, $a$ and $b$.

The ZN proof probably involves hiding both base an exponent values. Since there are many users, they cannot jointly compute a master shared key nor any other shared secret.

Any idea? (Maybe another public key cryptosystem is better suited for this kind of ZNP.)

• Camenisch/Stadler paper "Proof Systems for General Statements about Discrete Logarithms" seems helpful, but I can't adapt my requirements to the system in the paper.
– SDL
Oct 31, 2012 at 17:07
• I closed the question by request of the asker. There is a clearer redo of this question. Oct 31, 2012 at 18:50

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 variations): given a list of ciphertexts, Alice randomly permutes and decrypts them and then outputs the list of plaintexts, and now Alice wants to prove in zero knowledge that she did this correctly, without revealing the linkage between ciphertexts and plaintexts. Sounds like exactly what you need.

P.S. It sounds like your system is a special case of a mixnet, with only two ciphertexts. You might be able to design a custom protocol, using a disjunctive zero-knowledge proofs. There's a standard way to prove $\phi \vee \psi$ in zero-knowledge, without disclosing which is true (assuming you have a zero-knowledge protocol for $\phi$ and a zero-knowledge protocol for $\psi$). Also, there's a standard way to prove that $m$ is a correct decryption of ciphertext $c$. So, you could try using these methods to prove that $(D(a)=m_1 \wedge D(b)=m_2) \vee (D(a)=m_2 \wedge D(b)=m_1)$. You'll probably want to use a proof of knowledge.

• What I didn't specify (for simplification) is that a commitment to m1 or m2 is also produced. Supposing that a disjunctive zero-knowledge is simple to construct, this is an example of a single case: Given (a,b,c) = (g^x1 , x2*(h^x1), h^x2) and (g,h) we must prove knowledge of x1 and x2. Is it clear?
– SDL
Oct 31, 2012 at 16:58
• (a,b) are an ElGamal pair, c is a deterministic commitment to x2, x1 is the ElGamal randomization value, x2 is the plaintext.
– SDL
Oct 31, 2012 at 17:02
• @SDL, I'm puzzled by your statement. I can't think of any mixnet that requires a shared secret. A basic mixnet protocol has only one party: the mixer (who permutes and re-encrypts/decrypts the ciphertexts provided as input, and then proves to the rest of the world that this computation was done correctly). I don't know how familiar you are with mixnets; might it be worth spending a little more time reviewing the variety of schemes and how they work?
– D.W.
Oct 31, 2012 at 17:03
• @SDL, if g,h,x2 are known to the verifier, you should be able to use standard techniques for proof of knowledge of a discrete log. If x2 is not known to the verifier, then I would need to understand better how the scheme works to have an opinion; however, if you have the freedom to pick a different, more convenient commitment scheme, I expect there'll probably be efficient solutions (e.g., using a zk proof that two El Gamal ciphertexts decrypt to the same plaintext).
– D.W.
Oct 31, 2012 at 17:08
• x2 is not known to the verifier.
– SDL
Oct 31, 2012 at 18:22