Paper 2022/354

Optimal Synchronous Approximate Agreement with Asynchronous Fallback

Diana Ghinea, Chen-Da Liu-Zhang, and Roger Wattenhofer


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 $\epsilon > 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 $\Delta$ 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 $t_s$ corruptions when the network is synchronous and $t_a$ corruptions when the network is asynchronous, for any $0\le t_a < n/3 \le t_s < n/2$ such that $t_a + 2 \cdot t_s < n$. We further show that our protocol is optimal by proving that achieving AA for $t_a + 2 \cdot t_s \ge 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.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Contact author(s)
ghinead @ ethz ch
2022-03-18: received
Short URL
Creative Commons Attribution


      author = {Diana Ghinea and Chen-Da Liu-Zhang and Roger Wattenhofer},
      title = {Optimal Synchronous Approximate Agreement with Asynchronous Fallback},
      howpublished = {Cryptology ePrint Archive, Paper 2022/354},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.