log in  |  register  |  feedback?  |  help  |  web accessibility
How to Share a Secret: Infinitely, Dynamically and Robustly
Ilan Komargodski - Cornell Tech
Friday, February 16, 2018, 12:00-1:00 pm Calendar
  • You are subscribed to this talk through .
  • You are watching this talk through .
  • You are subscribed to this talk. (unsubscribe, watch)
  • You are watching this talk. (unwatch, subscribe)
  • You are not subscribed to this talk. (watch, subscribe)

Secret sharing schemes allow a dealer to distribute a secret piece of information among several parties such that only qualified subsets of parties can reconstruct the secret. The collection of qualified subsets is called an access structure. The best known example is the k-threshold access structure, where the qualified subsets are those of size at least k. When k=2 and there are n parties, there are schemes where the size of the share each party gets is roughly log(n) bits, and this is tight even for secrets of 1 bit. In these schemes, the number of parties n must be given in advance to the dealer.

We consider the case where the set of parties is not known in advance and could potentially be infinite. Our goal is to give the t-th party arriving a small share as possible as a function of t. We present a scheme for general access structures and several schemes for variants of the k-threshold access structure in which at any point in time some bounded number of parties can recover the secret. Lastly, we discuss other classical notions such as robustness, and adapt them to the unbounded setting.

The talk is based on joint works with Moni Naor and Eylon Yogev, and with Anat Paskin-Cherniavsky.



Ilan Komargodski is a postdoctoral researcher at Cornell Tech, hosted by Prof. Rafael Pass and Prof. Elaine Shi.

He completed his Ph.D. at the Weizmann Institute of Science, where he was fortunate to have Prof. Moni Naor as his advisor. He received a M.Sc. also at the Weizmann Institute under the guidance of Prof. Ran Raz.

He is interested in foundations of theoretical computer science, with an emphasis on cryptography and its interplay with complexity theory. 

This talk is organized by Octavian Suciu