Anonymous Card Shuffling and its Applications to Parallel Mixnets
This work addresses security and anonymity challenges in parallel mixnets and related applications, offering incremental improvements with new analytical tools.
The paper tackles the problem of shuffling cards under adversarial observation, where an opponent knows initial positions and can track cards except when they are shuffled in a private buffer, with applications to parallel mixnets. It introduces a sum-of-squares metric for anonymity, leading to improved performance bounds for parallel mixnets and extensions to handle corrupted servers and adversarially injected messages.
We study the question of how to shuffle $n$ cards when faced with an opponent who knows the initial position of all the cards {\em and} can track every card when permuted, {\em except} when one takes $K< n$ cards at a time and shuffles them in a private buffer "behind your back," which we call {\em buffer shuffling}. The problem arises naturally in the context of parallel mixnet servers as well as other security applications. Our analysis is based on related analyses of load-balancing processes. We include extensions to variations that involve corrupted servers and adversarially injected messages, which correspond to an opponent who can peek at some shuffles in the buffer and who can mark some number of the cards. In addition, our analysis makes novel use of a sum-of-squares metric for anonymity, which leads to improved performance bounds for parallel mixnets and can also be used to bound well-known existing anonymity measures.