Paper 2023/449
Multidimensional Approximate Agreement with Asynchronous Fallback
Abstract
Multidimensional Approximate Agreement considers a setting of $n$ parties, where each party holds a vector in $\mathbb{R}^D$ as input. The honest parties are required to obtain very close outputs in $\mathbb{R}^D$ that lie inside the convex hull of their inputs. Existing Multidimensional Approximate Agreement protocols achieve resilience against $t_s < n / (D + 1)$ corruptions under a synchronous network where messages are delivered within some time $\Delta$, but become completely insecure as soon as a single message is further delayed. On the other hand, asynchronous solutions do not rely on any delay upper bound, but only achieve resilience up to $t_a < n / (D + 2)$ corruptions. We investigate the feasibility of achieving Multidimensional Approximate Agreement protocols that achieve simultaneously guarantees in both network settings: We want to tolerate $t_s$ corruptions when the network is synchronous, and also tolerate $t_a \leq t_s$ corruptions when the network is asynchronous. We provide a protocol that works as long as $(D + 1) \cdot t_s + t_a < n$, and matches several existing lower bounds.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. 35th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA ’23)
- Keywords
- Approximate AgreementMultidimensional Approximate Agreementhybrid protocols
- Contact author(s)
-
ghinead @ ethz ch
chendaliu @ gmail com
wattenhofer @ ethz ch - History
- 2023-03-29: approved
- 2023-03-27: received
- See all versions
- Short URL
- https://ia.cr/2023/449
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/449, author = {Diana Ghinea and Chen-Da Liu-Zhang and Roger Wattenhofer}, title = {Multidimensional Approximate Agreement with Asynchronous Fallback}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/449}, year = {2023}, url = {https://eprint.iacr.org/2023/449} }