Monday February 16th at 4.30pm

(Or

whom must be a department manager. More generally, imagine a scenario where it is necessary to split up a

secret into shares and distribute those shares among a group of participants, such that only authorized

subsets of that group may recover the secret from their shares. The cryptographic tool for solving such

problems is called

We consider the problem of threshold secret sharing in
groups with hierarchical structure: a subset of

participants is authorized if it has at least *k_*0
members from the highest level, as well as at least

*k_*1 members from the two highest levels and so
forth. Such problems occur in settings where the

participants differ in their authority or level of
confidence and the presence of higher-level participants

is imperative to allow the recovery of the common secret.
Even though secret sharing in hierarchical groups has been

studied extensively in the past, none of the proposed solutions
addresses the simple setting that was described above.

We present a secret sharing
scheme for this problem that is both perfect and ideal. As in Shamir's scheme,

the secret is represented as the free coefficient of some
polynomial. The novelty of our scheme is the usage of

polynomial derivatives in order to generate lesser
shares for participants of lower levels. Consequently,

our scheme uses Birkhoff interpolation, i.e., the
construction of a polynomial according to an unstructured

set of point and derivative values.
Unfortunately, Birkhoff interpolation problems are not
always well posed.

Hence, a substantial part of our
study is dedicated to strategies that guarantee
well-posedness. Combining our

results with a duality result of A. Gal
regarding monotone span programs, we infer that the
closely related hierarchical

threshold access
structures that were studied by Simmons and Brickell
are also ideal. An explicit ideal scheme for

those problems is presented.