Conditional Disclosure of Secrets: Lower Bounds and Perspectives

Department of Computer Science and Automation
Department Seminar

Speaker : Dr. Prashant Vasudevan

Title : Conditional Disclosure of Secrets: Lower Bounds and Perspectives

Date : Monday, March 25, 2019

Time : 2:00 PM

Venue : CSA Seminar Hall (Room No. 254, First Floor)

Abstract :

Conditional Disclosure of Secrets (CDS), introduced by Gertner et al in 2000, is a minimal model of secure multi-party computation. Alice and Bob, who hold n-bit inputs x and y respectively, wish to release a common secret z to Carol (who knows both x and y) if and only if the input (x, y) satisfies some predefined predicate f. Alice and Bob are allowed to send a single message to Carol which may depend on their inputs and some shared randomness, and the goal is to minimize the communication complexity while providing information-theoretic security.

CDS protocols have applications to numerous cryptographic tasks, such as Private Information Retrieval and constructing Attribute-Based Encryption schemes, and are behind recent breakthrough constructions of secret sharing schemes with sub-exponential-sized shares for general access structures.

In this talk, I will present what we have learnt so far about the complexity of CDS rotocols, focusing on lower bounds and connections to communication complexity and the study of statistical zero-knowledge proofs, based on joint work with Benny Applebaum, Barak Arkis, and Pavel Raykov.

Biography of the speaker :

The speaker is a postdoctoral researcher at UC Berkeley, hosted by Sanjam Garg. He graduated from MIT last year, where he was advised by Vinod Vaikuntanathan. His research interests include Complexity Theory, Cryptography, and especially the things in between.

Host Faculty : Dr. Bhavana Kanukurthi


Scroll Up