Lower Bounds. In order to formulate the strongest impossibility results related to Approximate Agreement in the Mobile Byzantine faults model we examine a weaker version of this problem referred in [11] as Simple Approximate Agreement. Each correct node has a real value from [0, 1] as input and chooses a real value. Correct behav- iors must satisfy the following properties: Agreement: The maximum difference between values chosen by correct nodes must be strictly smaller than the maximum difference between the inputs, or be equal to the latter difference if it is zero. Validity: Each correct node chooses a value in the range of the inputs of the nodes. We prove lower bounds for each Mobile Byzantine faults models: Garay’s (M1), Bonnet’s(M2), Sasaki’s (M3) and Burhman’s (M4). The bounds for the models (M3) and (M4) result from the classical bounds proved in [11] and the mapping defined in Section 3. In the case of models (M1) and (M2), since the behavior of cured processes cannot be totally controlled by the Byzantine adversary, specific proofs are needed.
Lower Bounds. In this section we give lower bounds on the number of random variables used in a one-message key agreement protocol. The lower bounds match the usage in our protocols in the dominating terms. |→ We first give a theorem (Theorem 3.17) which states that for any distri- bution PXYZ no protocol for one-message key agreement has higher rate than S (X; Y Z). This was already proven in [AC93] for the case where n goes to infinity; we use the same method to give a quantitative statement which holds for any (finite) n. Further, we show (Theorem 3.18) that there exist distributions PXYZ for which it is impossible to obtain more than n(S→(X; Y|Z) — √1 — β √κ) — key bits with secrecy 1 2—κn and equal soundness from n random xxxx- xxxxx. In other words, for some distributions the dependence of the num- ber of random variables in terms of κ is optimal up to constant factors in our protocol which uses a random linear code (cf. Theorem 3.13).
