Discrete Mathematics and Optimization Seminar

The Open University and Ben Gurion University
Monday February 16th at 4.30pm
Burnside 1205

Title. Hierarchical Threshold Secret Sharing.
(Or "Why it wouldn't hurt bankers to know Birkhoff interpolation".)

Abstract. Imagine a bank where each fund transfer of over $1M must be signed by three employees, at least one of
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 secret sharing schemes and it was introduced, independently, by A. Shamir and G. Blakley.

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.