I am writing an exercise in cryptography about anonymous communication. One of the systems I have looked into is the mix net protocol. I want to prove that this is secure. I have seen many different ways of doing this, i.e. using a zero knowledge proof, but I don´t completely understand this.

Is there anyone who has a good explanation of why the mix net is secure?


1 Answer 1


Security in mixnets usually means two things. Anonymity and integrity.

For anonymity a single honest mix server suffices. Even if all other mix servers cooperate by releasing their permutations a message cannot be tracked, since the honest one does not publish his permutation. As a result it is lost when it reaches it.

For integrity zero knowledge proofs can be used.

Imagine you have a 2x2 reencryption mixnet with inputs: $C_1 = Enc(m_1,r_1)$ and $C_2 = Enc(m_2,r_2)$.

The mixnet reencrypts the inputs and computes ${C'}_1 = Reenc(C_1)=Enc(m_1,r_1+r_1')$ and ${C'}_2 = Reenc(C_2)=Enc(m_2,r_2+r_2')$.

Then it selects a random bit $b$ and outputs $({C'}_1, {C'}_2)$ if $b=0$ and $({C'}_2, {C'}_1)$ if $b=1$.

In order to prove integrity one must prove that the output is a reencryption of the input without revealing the value of $b$. More specifically the statement $(C'_1 = Reenc(C_1) \wedge C'_2 = Reenc(C_2)) \bigvee (C'_1 = Reenc(C_2) \wedge C'_2 = Reenc(C_1))$ must be proved in zero knowledge.

This can be done using composition of the Chaum - Pedersen Protocol for DLOG equality.

For more details you can check Rivest's course in http://courses.csail.mit.edu/6.897/spring04/materials.html


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.