Search

In this paper we focus on sender-anonymous channels (a.k.a. Dining Cryptographers networks) and present a construction requiring a very low (constant) number of rounds of interaction while tolerating actively malicious behavior by some of the participants (up to less than half of them). Our construction is unconditionally secure (meaning that no bounds are placed on the computational power of the adversary), makes black-box use of a verifiable secret sharing (VSS) protocol, and is based on a special-purpose secure multiparty computation protocol implementing the method of "throwing darts;" its round complexity is essentially equal to that of the VSS protocol.In addition, since broadcast cannot be simulated in a point-to-point network when a third or more of the participants are corrupt, it is impossible to construct VSS (and, more generally, any other basic multiparty protocol) in this setting without using a "physical broadcast channel," and a recent line of research has sought to minimize the use of this expensive resource. Our anonymous channel protocol's reduction to VSS is broadcast-round-preserving, thus making the fewest (known to date) calls to the broadcast channel while running in an overall constant number of rounds.Finally, anonymous channels play an important role in the setup phase of an authentication technique known as pseudosignatures, which then may be used to simulate authenticated Byzantine agreement protocols in the information-theoretic setting. Plugging in our anonymous channel translates into a fast (and broadcast-efficient) pseudosignature construction.

We describe an algorithm for fully-anonymous broadcast in large-scale networks. The protocol is similar to the dining cryptographers networks (DC-Nets) in that both are based on secure multi-party computation (MPC) techniques. However, we address the weaknesses of DC-Nets, which are poor scalability and vulnerability to jamming attacks. When compared to the state-of-the-art, our protocol reduces the total bit complexity from O(n2) to O(n) per anonymous message sent in a network of size n at the expense of an increase in total latency from O(1) to polylog(n). Our protocol can tolerate up to 1/3 dishonest parties, which are controlled by a static computationally-unbounded Byzantine adversary.

The paper describes an abstraction for protocols that are based on multiple rounds of Chaum's Dining Cryptographers protocol. It is proved that the abstraction preserves a rich class of specifications in the logic of knowledge. This result is applied to optimize model checking of implementations of a knowledge-based program that uses the Dining Cryptographers protocol as a primitive in an anonymous broadcast system. Performance results are given for model checking knowledge-based specifications in the concrete and abstract models of this protocol, and some new conclusions about the protocol are derived.

This paper describes an algorithm for model checking a fragment of the logic of knowledge and probability in multi-agent systems, with respect to a perfect recall interpretation of knowledge and agents' subjective probability. The algorithm has been implemented in the epistemic model checker MCK. Some experiments with the implemented algorithm are reported, in which some properties of agents' probabilistic knowledge are verified in two security protocols: Chaum's Dining Cryptographers protocol, and a protocol for Oblivious Transfer due to Rivest.

Epistemic protocols are communication protocols aiming at transfer of knowledge in a controlled way. Typically, the preconditions or goals for protocol actions depend on the knowledge of agents, often in nested form. Informal epistemic protocol descriptions for muddy children, coordinated attack, dining cryptographers, Russian cards, secret key exchange are well known. The contribution of this paper is a formal study of a natural requirement on epistemic protocols, that the contents of the protocol can be assumed to be common knowledge. By formalizing this requirement we can prove that there can be no unbiased deterministic protocol for the Russian cards problem. For purposes of our formal analysis we introduce an epistemic protocol language, and we show that its model checking problem is decidable.

There is a natural intuitive match between anonymity and information theory. In particular, the maximal anonymity loss in anonymity protocols can be matched to the information theoretical notion of channel capacity.However, there is also a significant mismatch between the theories and reality: current theories can only characterize channel capacity based upon certain assumptions of symmetry, which are rarely satisfied in the real world.This paper aims to resolve this mismatch by appealing to powerful mathematical techniques. A generic methodology using Lagrange multiplier method is proposed to characterize channel capacity in anonymity protocols.This Lagrangian approach is proved to be able to generalize previous work on the channel capacity of protocols. Further, we present analyses on three well known protocols, namely Dining Cryptographers, Crowds and Onion Routing to demonstrate the application of our methodology.