PhD Dissertation Defense: Laasya Bangalore
Title: “On Round-Efficient Black-Box Constructions of Cryptographic Protocols”
Cryptographic constructions have extensively been explored along three pivotal dimensions: underlying cryptographic assumptions, black-box usage, and round complexity. While significant strides have been made in demonstrating the theoretical feasibility of cryptographic protocols within these dimensions, practical efficiency has often been overlooked. This dissertation bridges this gap by developing constant-round cryptographic protocols that not only employ black-box techniques and require minimal assumptions but also prioritize practical efficiency. This work presents three key contributions:
First, we design a protocol for secure aggregation, essential for applications in federated learning and statistics collection. Our protocol ensures liveness, protects against faulty inputs, and offers security against malicious clients. In federated learning, it securely aggregates local models without exposing sensitive data, mitigates model poisoning attacks, and scales efficiently to thousands of clients with constant round efficiency and competitive costs. Beyond the standard single-server setting, we also develop protocols for a multi-server setting, which tolerates a stronger adversarial model. Furthermore, we incorporate differential privacy to enhance the security guarantees.
Second, we design a time and space-efficient zero-knowledge proof system with sub-linear communication complexity for NP relations verifiable in non-trivial space, based on collision-resistant hash functions (CRH). Our system minimizes overhead in time and space, allowing both the prover and verifier to run efficiently while maintaining low communication costs. Additionally, we provide evidence that further reducing proof lengths poses significant challenges with currently symmetric-key techniques.
Third, we develop a two-round, adaptively secure two-party computation (2PC) protocol specifically designed for RAM programs and is secure against full corruption. Notably, we improve the communication complexity to be proportional to the square of the RAM complexity rather than square of boolean circuit complexity, thereby overcoming the inefficiencies associated with converting RAM programs to circuits.
Committee members:
Muthu Venkitasubramaniam (adviser)
Kobbi Nissim
Micah Sherr
Carmit Hazay (Bar-Ilan University)