**Optimal Synchronous Approximate Agreement with Asynchronous Fallback**

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

**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 $\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.

**Category / Keywords: **cryptographic protocols /

**Date: **received 14 Mar 2022

**Contact author: **ghinead at ethz ch

**Available format(s): **PDF | BibTeX Citation

**Version: **20220318:094419 (All versions of this report)

**Short URL: **ia.cr/2022/354

[ Cryptology ePrint archive ]