Checking Phase. Here the parties, on having private input message of A bits each (i.e. miα’s), jointly perform some computation in order to determine and agree on a set of tj + 1 parties called cjh j, such that the honest parties in cjh hold a common A/t bit message, say mα∗ . In case of failure due to the inconsistencies among the inputs of the honest parties, the parties abort any further computation for current segment and agree on a predefined message m†α. So in this case current segment terminates with all honest parties agreeing on common output m∗α = mα† . On the other hand, if cjh is generated and agreed among the parties, then the computation for current segment proceeds to the next phase. It is to be noted that Pcjh will be always obtained if the initial messages of the honest parties in Pj are same. P P P P P P ⊂ P ⊆ P P
Checking Phase. Participate in the code Checking, presented in Fig. 1 to in P hold common bits, say m . If P is generated then proceed to the determine and agree on Pcjh ⊆ Pj of size tj + 1 such that all the honest parties ch j Æ t cjh α = α + 1 and terminate the current segment with output m∗α.
Checking Phase. As mentioned before, the aim of this phase is to either agree on a set cjh of size tj + 1 such that all the honest parties in cjh hold common message, say mα∗ , or decide that such set may not exist. When all the honest parties start with same input message, cjh can be always found out and agreed upon. To achieve the above task, every party hashes his message with a random key and A-casts the (random key, hash value) pair. The parties then agree on a set of nj tj parties whose A-cast will be eventually received by every honest party. This can be achieved by executing an instance of ACS. Now every party Pi prepares a response vector →−vi , indicating whether the ∈ I hash value of every Pj is indeed the hash value of his own message miα with respect to Pj’s hash key (this should ideally be the case, when Pi and Pj are honest and their input messages are identical, i.e. miα = mjα). Pi A-casts − J →−vi . Now the parties again agree on a set of nj tj parties, say whose A-cast with their →−vi has been terminated. Now notice that if all honest parties start with J P I J P P common input, then the vectors of the honest parties in would be identical and would have at least tj + 1 1’s at the locations corresponding to the tj + 1 honest parties in . So now the parties try to find a set of at least tj + 1 parties in , whose vectors are identical and have at least tj + 1 1’s in them. If found, then any subset of tj + 1 parties from that set (say tj + 1 parties with smallest index) will be considered as cjh. It is easy to show that cjh will be always obtained if the initial messages of the honest parties in j are same. Moreover it can be P P shown that the honest parties in cjh hold common message, say m∗α with very high probability (see Lemma 2). But if cjh is not found, then the honest parties know that their input messages are inconsistent and hence they agree that such set can not be found. The steps performed so far are enough for achieving the goal of our current phase. I
