1
$\begingroup$

In this paper secret sharing is to distribute information (the secret) over a set of participants such that the secret can only be reconstructed if certain authorized combinations of participants join their information. The set of authorized combinations is called the access structure.

Formally, the secret is modeled as a random variable S, and a secret sharing scheme assigns a random variable $X_i$ to each participant $i$ in such a way that if $\{ i_ 1, . . . , i_ k \} $is an authorized set of participants, then S is a function of $X_ {i_1}, . . . , X_{ i_ k}$ that is, $H ( S |X_ {i_1}, . . . , X_{ i_ k} ) = 0$;

Here my doubt is $X_ {i_1}, . . . , X_{ i_ k}$ are IID random variables or not

$\endgroup$

1 Answer 1

2
$\begingroup$

My first understanding was yes, but in fact, it depends.

First understanding: You can view them as IID, unless you have some knowledge about the secret $s$ and enough other variables. Take for example a Shamir Secret, a simpler secret sharing scheme which is a special case of this. A Shamir secret allows to reconstruct $s$ with any set of $k$ parts from $n$ shares. It is built by choosing a random $k-1$ degree polynomial such that $f(0)=s$. Any set of $k$ or more distinct points allows you to reconstruct this polynomial curve and thus learn it's value for $x=0$. Any set of $k-1$ points (except $(f(0),0)$) would be unauthorized and insufficient to reconstruct the secret. Since each coefficient of the polynomial (except $s$, that you have no knowledge of, including it's distribution) is chosen randomly, every set of point. Conditioning on $k-1$ shares doesn't change in any way the distribution of the $k^{th}$ share: it is still random.

But in fact it's not necessarily the case: only parts of these shares must be randomly distributed. Take these Shamir secrets: every share is a tuple $(x,f(x))$, and given their construction and a tuple $(x_1,f(x_1))$, you would expect the next tuple not to have $x_2 \neq x_1 $, so that even if $f(x_2)$ would be independent of $(x_1,f(x_1))$, $(x_2,f(x_2))$ would not. Conversely, you could choose $x$ as random every time, risking a possible $x_2 = x_1$, but making all the shares IID.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.