Plausible Deniability for Anonymous Communication

The rigorous analysis of anonymous communication protocols and formal privacy goals have proven to be difficult to get right. Formal privacy notions as in the current state of the art based on indistinguishability games simplify analysis. Achieving them, however can incur prohibitively high overhead in terms of latency. Definitions based on function views, albeit less investigated, might imply less overhead but aren't directly comparable to state of the art notions, due to differences in the model. In this paper, we bridge the worlds of indistinguishability game and function view based notions by introducing a new game: the "Exists INDistinguishability" (E-IND), a weak notion that corresponds to what is informally sometimes termed Plausible Deniability. By intuition, for every action in a system achieving plausible deniability there exists an equally plausible, alternative that results in observations that an adversary cannot tell apart. We show how this definition connects the early formalizations of privacy based on function views[13] to recent game-based definitions. This enables us to link, analyze, and compare existing efforts in the field.