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

Question

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

Answer 1

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.