Collusion-Free Protocols in the Mediated Model

Prior approaches [15, 14] to building collusion-free protocols
require exotic channels. By taking a conceptually new approach, we are
able to use a more digitally-friendly communication channel to construct
protocols that achieve a stronger collusion-free property.

We consider a communication channel which can filter and rerandomize
message traffic. We then provide a new security definition that captures
collusion-freeness in this new setting; our new setting even allows for the
mediator to be corrupted in which case the security gracefully fails to
providing standard privacy and correctness. This stronger notion makes
the property useful in more settings.

To illustrate feasibility, we construct a commitment scheme and a zero-
knowledge proof of knowledge that meet our definition in its two variations.

[pdf]