(2022) Efficient Adaptively-Secure Byzantine Agreement for Long Messages.
|
Text
2021-1403.pdf Download (917kB) | Preview |
Abstract
We investigate the communication complexity of Byzantine agreement protocols for long messages against an adaptive adversary. In this setting, prior $n$-party protocols either achieved a communication complexity of $O(nl\cdot\poly(\kappa))$ or $O(nl + n^2 \cdot \poly(\kappa))$ for $l$-bit long messages and security parameter $\kappa$. We improve the state of the art by presenting protocols with communication complexity $O(nl + n \cdot \poly(\kappa))$ in both the synchronous and asynchronous communication models. The synchronous protocol tolerates $t \le (1-\epsilon) \frac{n}{2}$ corruptions and assumes a VRF setup, while the asynchronous protocol tolerates $t \le (1-\epsilon) \frac{n}{3}$ corruptions under further cryptographic assumptions. Our protocols are very simple and combine subcommittee election with the recent approach of Nayak et al. (DISC `20). Surprisingly, the analysis of our protocols is \emph{all but simple} and involves an interesting new application of Mc Diarmid's inequality to obtain {\em almost optimal} corruption thresholds.
| Item Type: | Conference or Workshop Item (A Paper) (Paper) |
|---|---|
| Divisions: | Julian Loss (JL) |
| Conference: | ASIACRYPT International Conference on the Theory and Application of Cryptology and Information Security |
| Depositing User: | Julian Loss |
| Date Deposited: | 21 Oct 2022 07:07 |
| Last Modified: | 21 Oct 2022 07:07 |
| Primary Research Area: | NRA1: Trustworthy Information Processing |
| URI: | https://publications.cispa.saarland/id/eprint/3866 |
Actions
Actions (login required)
 |
View Item |