PhD Dissertation Proposal: Laasya Bangalore
Title: “On Round-Efficient Black-Box Constructions of Cryptographic Protocols”
Cryptographic constructions have been extensively studied along three fundamental lines: underlying cryptographic assumptions used, black-box usage, and round complexity. While much research has concentrated on establishing the feasibility of cryptographic protocols within these areas, there has been less focus on ensuring that these constructions are also practically efficient. This proposal aims to address this gap by developing constant-round cryptographic protocols that not only employ black-box techniques and require minimal assumptions but also prioritize practical efficiency. The proposal presents three such cryptographic protocols, as follows.
First, we study time and space-efficient sublinear arguments: We design a zero-knowledge proof system with sublinear communication complexity for NP relations verifiable in non-trivial space, based on collision-resistant hash-functions (CRH). Our system achieves efficiency by minimizing the overhead in time and space, allowing the prover and verifier to run efficiently while keeping communication costs low. We also provide evidence that further reducing proof length is challenging with current symmetric-key techniques.
Second, we design a protocol for secure aggregation, a fundamental task with applications in federated learning and statistics collection. Our protocol ensures liveness, robustness (safeguards against faulty inputs), and security against malicious clients. In federated learning, it securely aggregates local models without revealing sensitive data, mitigates model poisoning attacks, and scales to thousands of clients with constant round efficiency and competitive costs.
Third, we study adaptively secure computation for RAM programs. We develop a two-round, adaptively secure two-party computation (2PC) protocol for RAM programs, addressing the inefficiencies of converting RAM programs to circuits. Our protocol, secure against full corruption using non-committing encryption, achieves communication complexity proportional to the square of the RAM complexity, enhancing practical efficiency for secure computations.
Committee members:
Muthu Venkitasubramaniam (adviser)
Kobbi Nissim
Micah Sherr
Carmit Hazay (Bar-Ilan University)