Paper 2013/105

Lossy Chains and Fractional Secret Sharing

Yuval Ishai, Eyal Kushilevitz, and Omer Strulovich

Abstract

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 {\em lossy chains} and {\em 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 $$ by guaranteeing that from the point of view of each set $$ of parties, the secret is {\em uniformly} distributed over a set of $$ potential secrets. We show that every (monotone) fractional access structure can be realized. For {\em symmetric} structures, in which $$ depends only on the size of $$, we give an efficient construction with share size $$. Our construction of fractional secret sharing schemes is based on the new notion of {\em lossy chains} which may be of independent interest. A lossy chain is a Markov chain $$ which starts with a random secret $$ and gradually loses information about it at a rate which is specified by a {\em loss function} $$. Concretely, in every step $$, the distribution of $$ conditioned on the value of $$ should always be uniformly distributed over a set of size $$. We show how to construct such lossy chains efficiently for any possible loss function $$, and prove that our construction achieves an optimal asymptotic information rate.