We consider the case where the set of parties is not known in advanced and could potentially be infinite. Our goal is to give the party arriving at step t a small share as possible as a function of t. Our main result is such a scheme for the kk-threshold access structure where the share size of party tt is (k−1)log t plus o(logt)poly(k). For k=2 we observe an equivalence to prefix codes and present matching upper and lower bounds of the form logt+loglogt+logloglogt+...+O(1)).
Finally, we show that for any access structure there exists such a secret sharing scheme with shares of size 2^(t−1).
Paper: PDF Slides: A HREF="http://www.wisdom.weizmann.ac.il/~naor/PAPERS/evolving_ss.pptx">PPT .
Back to On-Line Publications