Omer Strulovich, M.Sc. Thesis Seminar
Wednesday, 21.11.2012, 15:30
A rich man has many children. Unfortunately, over the years they have grew
apart and started to hate each other. The rich man seeks to
give his inheritance to the largest group of his children that can cooperate.
How can he do it?
To answer this, we introduce and study the related notions
of lossy chains and fractional secret sharing.
Both of these concepts are motivated by goal of controlling the amount of
work required in order to solve a cryptographic puzzle, or access a shared resource.
Fractional secret sharing generalizes traditional secret sharing
by allowing a fine-grained control over the amount of uncertainty
about the secret.
More concretely, a fractional secret sharing scheme realizes a fractional
access structure f:2^[n]->[m] by guaranteeing that from the point
of view of each subset of parties T, the secret is uniformly distributed
over a set of f(T) potential secrets.
We show that every (monotone) fractional access structure can be realized.
For symmetric structures, in which f(T) depends only on the size of T,
we give an efficient construction with share size poly(n,log m).
Our construction of fractional secret sharing schemes is based the new
notion of lossy chains which may be of independent interest.
A lossy chain is a Markov chain (X_0,...,X_n) which starts with
a random secret X_0 and gradually loses information about it at a rate
which is specified by a loss function g. Concretely, in every step t,
the distribution of X_0 conditioned on the value of X_t should always
be uniformly distributed over a set of size g(t).
We show how to construct such lossy chains efficiently for any possible
loss function g, and prove that our construction achieves an optimal
asymptotic information rate.