M.Sc Student | Strulovich Omer |
---|---|

Subject | Lossy Chains and Fractional Secret Sharing |

Department | Department of Computer Science |

Supervisors | Professor Yuval Ishai |

Professor Eyal Kushilevitz | |

Full Thesis text |

Motivated by the goal of controlling the amount of work required to access a shared resource or to solve a cryptographic puzzle, we introduce and study the related notions of lossy chains and fractional secret sharing.

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 set T\subseteq [n] of parties, 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 on 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

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.