Hierarchy of Three-Party Consistency Specifications

In the theory of distributed systems and in cryptography one considers a set of n parties which wish to securely perform a certain computation, even if some of the parties are dishonest. Broadcast, one of the most fundamental and widely used such primitives, allows one (possibly cheating) party to distribute a value m consistently to the other parties, in a context where only bilateral (authenticated) channels between parties are available. A well-known result [LSP82] states that this is possible if and only if strictly less than a third of the parties are dishonest. Broadcast guarantees a very strong form of consistency. This paper investigates generalizations of the broadcast setting in two directions: weaker forms of consistency guarantees are considered, and other resources than merely bilateral channels are assumed to be available. The ultimate goal of this line of work is to arrive at a complete classification of consistency specifications [Mau04]. As a concrete result in this direction we present a complete classification of three-party specifications with a binary input and binary outputs.