Paper 2022/354

Optimal Synchronous Approximate Agreement with Asynchronous Fallback

Diana Ghinea, 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 ϵ>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 Δ 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 corruptions when the network is synchronous and corruptions when the network is asynchronous, for any such that . We further show that our protocol is optimal by proving that achieving AA for is impossible (even with setup). Remarkably, this is also the first AA protocol that tolerates more than corruptions in the synchronous network model.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Contact author(s)
ghinead @ ethz ch
History
2022-03-18: received
Short URL
https://ia.cr/2022/354
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/354,
      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},
      url = {https://eprint.iacr.org/2022/354}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.