Mix-networks, a family of anonymous messaging protocols, have been engineered to withstand a wide range of theoretical internal and external adversaries. An undetectable insider threat—voluntary partial trace disclosures by server administrators—remains a troubling source of vulnerability. An administrator's cooperation could be the resulting coercion, bribery, or a simple change of interests. While eliminating this insider threat is impossible, it is feasible to deter such unauthorized disclosures by bundling them with additional penalties. We abstract these costs with collateral keys, which grant access to customizable resources. This article introduces the notion of trace-deterring mix-networks, which encode collateral keys for every server-node into every end-to-end message trace. The network reveals no keying material when the input-to-output transitions of individual servers remain secret. Two permutation strategies for encoding key information into traces, mix-and-flip and all-or-nothing, are presented. We analyze their trade-offs with respect to computational efficiency, anonymity sets, and colluding message senders. Our techniques have sufficiently low overhead for deployment in large-scale elections, thereby providing a sort of publicly verifiable privacy guarantee.

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 practical concern