Deterring Voluntary Trace Disclosure in Re-encryption Mix Networks
P. Golle, X. Wang, M. Jakobsson and A. Tsow.
An all too real threat to the privacy offered by a mix network is that
individual mix administrators may volunteer partial tracing information to
a coercer. While this threat can never be eliminated -- coerced
mix servers could simply be forced to reveal all their secret data -- we can
deter administrators from succumbing to coercive attacks by raising
the stakes. We introduce the notion of a trace-deterring mix
permutation to guarantee privacy, and show how it ensures that a
collateral key (used for an arbitrary purpose) be automatically
revealed given any end-to-end trace from input to output elements.
However, no keying material is revealed to a party who simply knows
what input element corresponds to what output element. Our techniques are
sufficiently efficient to be deployed in large-scale elections, thereby
providing a sort of publicly verifiable privacy guarantee. Their impact on
the size of the anonymity set -- while quantifiable -- are not of