Paper 2023/449

Multidimensional Approximate Agreement with Asynchronous Fallback

Diana Ghinea, ETH Zurich
Chen-Da Liu-Zhang, NTT Research
Roger Wattenhofer, ETH Zurich
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)
PDF
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.