Boston University
Towards better asynchronous systems: advances in cryptography and distributed protocols
Abstract
dc:description.abstractThis thesis presents advancements in three foundational primitives of distributed systems and cryptography, all within the asynchronous setting. 1.Asynchronous Byzantine reliable broadcast (BRB) protocols enable a dealer to send a message to n parties in a consistent way, even in the presence of Byzantine failures. If a message is accepted as valid by an honest party, then all honest parties will also accept the same message as valid. These protocols are essential for achieving consensus and coordination in distributed systems, providing a foundation for more complex protocols such as Byzantine Agreement and State Machine Replication. However, BRB is considered weaker than Byzantine Agreement because it does not guarantee termination if a malicious dealer fails to broadcast a message. We present several reliable broadcast protocols that push the state of the art in terms of communication complexity closer to the lower bound. Some of these protocols are practical, while others are more theoretical. 2. Asynchronous Verifiable Information Dispersal (AVID) protocols enable a dealer to disperse a message M across a collection of parties so that a threshold k of the group can reconstruct M. AVID focuses on reducing the storage requirements needed by the k parties while maintaining data integrity and availability. As such every BRB is an inefficient AVID. These protocols are crucial for optimizing resource usage in distributed storage systems and facilitating provable efficient data retrieval or communication. We contribute a new AVID construction that achieves optimal storage, support for retrieving only parts of the message, and guaranteed output delivery while maintaining optimal asymptotic communication complexity during dispersal and retrieval. This is accomplished by combining a few technical innovations. We obtain optimal storage by separating the honest thresholds needed for consensus and for retrieval. We support partial retrievals and guaranteed delivery by using bi-dimensional erasure coding and a novel committing technique that combines vector and polynomial commitments to detect malicious behavior by the dealer at dispersal time, whereas prior work deferred this detection to retrieval. 3.Asynchronous Verifiable Secret Sharing (AVSS) protocols also allow a dealer to disperse a message M across a collection of parties, but with a focus on preserving privacy. AVSS ensures that if a group of fewer than k parties tries to reconstruct the message, they learn nothing about M. As such, every AVSS is an AVID. This privacy-preserving feature is vital for secure multiparty computations, secret leader election, common randomness generation, Byzantine agreement, and distributed key generation. We present several AVSS constructions, the first AVSS with optimal worst case communication complexity and the first AVSS with optimal worst case amortized communication complexity. Along the way, we also provide a construction for an ADKG that is based on our AVSS that can achieve for the first time optimal amortized communication complexity in the worst case, without a trusted dealer.
Degree
thesis:*- Name thesis:degree_name
- Doctor of Philosophy
- Level thesis:degree_level
- doctoral
- Discipline thesis:degree_discipline
- Computer Science
- Grantor
- Boston University
- Year dc:date.issued
- 2025
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Alhaddad, Nicolas
- Advisor dc:contributor.advisor
-
- Varia, Mayank
Subjects
dc:subject × 1Rights
dc:rights- Statement dc:rights
-
- Attribution 4.0 International
- Licence dc:rights.uri
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/2144/53248