Assume that. ΠABA is an asynchronous protocol for byzantine agreement that guarantees validity, con- sistency, and p-termination if less than nfAR parties are dishonest and satisfies validity if less than nfAV parties are dishonest. • ΠSBA is a synchronous protocol for byzantine agreement that guarantees validity and con- sistency, given that less than n parties are corrupted. ΠSBA runs in time tSBA ≤ f (n)∆ for some function f (n) that does not depend on ∆. • 1 > fAV ≥ fAR. Then the following statements are true: 1 start • If fAR ≤ 4 and for all Pi, tout − ti ≥ ∆ then ΠHBA is (p, fAR)-output responsive. • ΠHBA is 2 -consistent. • ΠHBA is fAV-valid. • ΠHBA terminates at time tout + ∆ + tSBA.
Assume that prg is a (tprg, εprg)-secure pseudo-random generator, – Π is a (tcpa, εcpa)-CPA-secure updatable public-key encryption scheme, and – Σ is a (tcma, ϵcma)-CMA-secure ratcheting digital signature scheme. TreeKEMΣ∗ is then (t, c, n, P, ϵ)-adaptive secure CGKA-FA for P ∈ {tkm, pcsau, fsau}. Note that ϵ = 2cn(ϵprg + ϵcpa) +(c − 1)ϵcma, t ≈ tprg ≈ tcpa ≈ tcma are held. Proof of Theorem. To prove the above theorem, we introduce the helpful lem- mas. The following lemma deals with the relationships among the tkm, pcsau, and fsau predicates.
Assume that. ΠABA is an asynchronous protocol for byzantine agreement that guarantees validity, con- sistency, and p-termination if less than nfAR parties are dishonest and satisfies validity if less than nfAV parties are dishonest. • ΠSBA is a synchronous protocol for byzantine agreement that guarantees validity and con- sistency, given that less than n parties are corrupted. ΠSBA runs in time tSBA ≤ f (n)∆ for some function f that does not depend on ∆. par • ΠSBC is a synchronous protocol for all-to-all byzantine broadcast that runs in time (at most) tSBC. • 1 > fAV ≥ fAR. start Then the following statements are true: 1 • If fAR ≤ 4 • ΠETHBA is and for all honest Pi, tout — ti n -consistent. > ∆ then ΠHBA is (p, fAR)-responsive. • ΠETHBA is fAV-valid. • ΠETHBA terminates at time t ≤ tout + tSBC + tSBA + ∆.
