Optimal Synchronous Approximate Agreement with Asynchronous Fallback

Abstract

Approximate Agreement (AA) allows a set of n parties that start with real-valued inputs to obtain values that are at most within a parameter ε > 0 from each other and within the range of their inputs. Existing AA protocols, both for the synchronous network model (where any message is delivered within a known delay Δ time) and the asynchronous network model, are secure when up to t < n/3 of the parties are corrupted and require no initial setup (such as a public-key infrastructure (PKI) for signatures). We consider AA protocols where a PKI is available, and show the first AA protocol that achieves simultaneously security against ts corruptions when the network is synchronous and ta corruptions when the network is asynchronous, for any 0 ≤ ta < n/3 ≤ ts < n/2 such that ta + 2 · ts < n. We further show that our protocol is optimal by proving that achieving AA for ta +2·ts ≥ n is impossible (even with setup). Remarkably, this is also the first AA protocol that tolerates more than n/3 corruptions in the synchronous network model.