Output Phase. The segment failure may occur only in the second phase and hence only the first two phases of a segment may be repeated several times (bounded by t); once the first two phases are successful for a segment, the segment will always be successfully completed after robustly executing the third phase. So at the end of segment α, every honest party will t agree on a common A bits, denoted by m∗α. Moreover if the honest parties start with common input (i.e. miα’s are equal for all honest parties), then m∗α will be same as that common input. t
Output Phase. Here the parties in Pe′x help the parties in P \Pe′x (not P′ \ Pe′x) to learn the common l/t message m held by the honest parties in Pe′x. After this phase, current segment terminates with common output m∗α and the parties proceed to the computation of next segment. The implementation of this phase is very similar to the implementation of the Output Phase of [21] and the Claiming Stage of the BA protocol of [15]. Now the overall structure of Optimal-ABA is presented below. Protocol Optimal-ABA(P) Code for Pi: Every party in P executes this code.
1. Set n' = n, t' = t and P' = P. Initialize α = 1.
2. While α ≤ t, do the following for segment Sα with input miα and with n', t' and P' to agree on m∗α:
Output Phase. Here the (honest) parties in CORE propagate the common message held by them (which they have received from S) to all other (honest) parties in P \ CORE. Informally, in Distribution Phase, S sends his message m to every party in . In Verification & Agreement on CORE Phase, party Pi on receiving a message, say mi from S, computes n hash values of mi corresponding to n distinct random hash keys, say ri1, . . . , rin chosen from F. To enable Pj to check whether his received message mj is same as Xx’s received message mi, party Pi privately sends rij and ij = κ(mi, rij) to Pj. Party Pj, on receiving these values from Pi checks whether ij = κ(mj, rij) (for honest S and Pi, it should hold). Xx Xxxxxx-A-casts a confirmation signal OK(Pj, Pi) if the above check passes. Now based on the confirmation signals, a graph with the parties in as vertex set is formed and applying Find-STAR on the graph, an (n, t)-star ( , ) is obtained. The ( , ) is then agreed among all the parties and component of it is taken as CORE. The protocols for Distribution Phase and Verification & Agreement on CORE Phase are given below. Before outlining Output Phase, we prove Lemma 1-3.
Output Phase. The segment failure may occur only in first phase and hence only the first phase of a segment may be repeated several times (bounded by t); once the first phase is successful for a segment, the segment will always be successfully completed after robustly executing second phase.
Output Phase. Here the parties in CORE help the parties in P \ CORE (not P' \ CORE) to learn the common l/t message m∗α held by the honest parties in CORE. After this phase, current segment terminates with common output m∗α and the parties proceed to the computation of next segment. The purpose and the implementation of this phase is almost identical to the Output Phase of Optimal-A-cast. Now the overall structure of Optimal-ABA is as follows: Code for Pi: Protocol Optimal-ABA(P)
1. Set n' = n, t' = t and 9' = 9.
2. For each segment Sα with input miα (α = 1, . . . , t) do the following with current n', t' and 9' to agree on m∗α:
1. Verification & Agreement on CORE Phase:
(a) Generation of K/Generation of CORE in case of Failure: Replicate Code-I (presented later).
(b) CORE Generation by expanding K to contain 2t' +1 parties: Replicate Code-II (presented later).
Output Phase. Same as protocol Output in Optimal-A-cast with t being replaced by t', l being replaced by Æ . Moreover, CORE contains 2t' + 1 parties and CORE = 9 \ CORE.
Output Phase. Output 1 if and only if Verify(pp, {vk1, . . . , vkn}, m′, σ′) = 1 and m′ =ƒ m.
(a) A chooses a subset S ⊆ [n] \ I such that |S ∪ I| < n/3. It also chooses messages m and Definition 3.4 (Unforgeability). Let t < n/3. An SRDS scheme Π is t-unforgeable with a bulletin- board PKI (resp., with a trusted PKI) if for mode = bb-pki (resp., mode = tr-pki) and for every (stateful) PPT adversary A it holds that Expt Pr forge mode,Π,A (κ, n, t) = 1 ≤ negl(κ, n). mode,Π,A The experiment Exptforge is defined in Figure 3. We note that as described, the security definition is only for one-time signatures. Although this is sufficient for our applications in Section 4, it is possible to extend the definition and provide the adversary an oracle access to signatures of honest parties on messages of its choice. However, in that case, the adversary must choose the set S before getting oracle access.
