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

-

## closed as not a real question by Paŭlo EbermannOct 31 '12 at 18:47

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

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.