The protocol designer should first specify what coalitions are to be allowed and forbidden. If the parties have rational self-interest, only coalitions whose members have an incentive to not collude, to either compute an incorrect result, or to violate the privacy of any player, should be allowed the potential to disrupt the protocol. Invoking "incentive" implies an economic or game-theoretic analysis of coalitions, which will be considered in a future article.
For now, we just observe that the protocol designer needs to draw from C a set of allowed ("good") coalitions GC. Any set of parties in GC is a coalition sufficient to successfully complete the protocol. Also draw from C set disjoint from GC of disallowed ("bad") coalitions BC which cannot be allowed the opportunity to disrupt the protocol. If GC union BC = C then we say that the partition is unambiguous. Also, the sets in GC are the complements of the sets in BC, and vice versa.
To produce a secure protocol, these coalitions need to meet certain criteria. Particularly interesting is the quorum system, a set of good coalitions, every member of which intersects in at least one party. Each quorum can act on behalf of the system to complete the protocol. Intersection facilitates consistency across quorums. For example, if an operation occurs in two quorums, then at least one party observes both. Indeed, a fault-tolerant or secure quorum system intersects in a set containing sufficiently many parties to guarantee correctness. See, for example, the masking and dissemination quorum systems used by Malkhi & Reiter [MR97] to design a replicated database secure against Byzantine faults by bad coalitions.
[BW98], following the trail blazed by among others [HM97] and [NW96], have shown that if any single party can be trusted with correctness, then a quorum system is necessary and sufficient for the privacy of inputs to a multiparty computation[S97] against resource unbounded adversaries. Classical analysis of multiparty computation concluded that a threshold of more than half of the parties is necessary and sufficient for private computation. This is just a special case of BW98 result. Any threshold system whose threshold exceeds N/2 is also a quorum system -- there are only N parties, so two coalitions of size >N/2 must contain at least one party in common, thus forming a quorum system.
The classical analysis also concluded that a majority threshold is necessary and sufficient for _correct_ multiparty computation, i.e. secure against active Byzantine faults in minorities with polynomial amounts of resources. A two-thirds majority is necessary against resource unbounded adversaries. I am aware of no correctness result as yet for quorum systems in multiparty computation.
M1: None of the sets of correct servers which contain the latest value is a bad coalition. To achieve this, any quorum intersection minus any bad colation should not be a subset of any other bad coalition. Formally: for all Q1,Q2 element of GC and all B1,B2 element of BC, (Q1 intersect Q2) - B1 is not a subset of B2.
M2: No bad coalition can disable all quorums. Formally: for all B element of BC there exists some Q element of GC such that B and Q are disjoint.
These constrains are suficient to ensure that a replicated database is updated consitently and correctly, iff |U|>4f.
D1: Any quorum intersection is not a subset of any bad coalition. Formally: for all Q1,Q2 element of GC and all B element of BC, (Q1 intersect Q2) is not a subset of B.
D2: No bad coalition can disable all quorums. Formally: for all B element of BC there exists some Q element of GC such that B and Q are disjoint.
These constrains are sufficient to ensure that a replicated database is updated consistently, iff |U|>3f. Correctness of the data must be ensured by some other means, e.g. external signing and verification of digital signatures.
Ref: BW98 D. Beaver and A. Wool, "Quorum-based Secure Multi-Party Computation", Eurocrypt '98, also at http://www.transarc.com/~beaver/research/publications/biblio.html#mpp HM97 M. Hirt and U. Maurer, "Complete characterization of adversaries tolerable in secure multi-party computation", 16th ACM PODC M91 R. Myerson, _Game Theory: Analysis of Conflict_ MR97 D. Maklhi & M. Reiter, "Byzantine Quorum Systems", 21st ACM STOC, also at http://www.research.att.com/~dalia/ For an important application of Byzantine tolerant replication, see http://szabo.best.vwh.net/securetitle.html NW96 M. Naor and A. Wool, "Access control and signatures via quorum secret sharing", 3rd ACM Conf. on Computer and Communications Security S96 On secure credit reporting, virus list distribution, etc.: http://szabo.best.vwh.net/negative_rep.html S97 A gentle introduction to multiparty computation and its potential applications: http://szabo.best.vwh.net/msc.html S98 Secure property titles: http://szabo.best.vwh.net/securetitle.html