Cryptology ePrint Archive: Report 2022/354

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