# 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 '12 at 17:07
• I closed the question by request of the asker. There is a clearer redo of this question. – Paŭlo Ebermann Oct 31 '12 at 18:50

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.