Complexity seminar

Adaptively-secure secret sharing

A secret-sharing scheme is used to distribute a secret between a
set of participants so that a subset of the participants that satisfy
certain conditions can reconstruct the secret. In the computational setting,
it is relatively easy to achieve selective security (where the adversary
commits a-priori to the set of corrupt participants), but appears difficult
to achieve the more natural notion of adaptive security (where the adversary
can corrupt participants as the attack progresses). It is well known that
selective security, where the adversary has to commit to n-bits of
information about his future choices, automatically implies adaptive
security at the cost of amplifying the adversary’s advantage by a factor of
up to 2^n. In this talk we will see how one can, in certain cases, achieve
better bounds than 2^n by using techniques from graph pebbling. 

(Based on joint work with Zahra Jafargholi, Karen Klein, Ilan Komargodski,
Krzysztof Pietrzak, and Daniel Wichs.)