# Reducing $n$ in $(n,k)$ secret sharing while keeping it effective

Assume Bob wants to share a secret with Alice. Assume he can only send messages using a one-sided channel which is insecure and unreliable. Unreliable, meaning: Alice only gets messages sent over this channel with probability $P$. Insecure, meaning: Mallory the bad guy can read any message sent over this channel with probability $P'$.

Assuming $P>P'$, Bob can use $(n,k)$-secret sharing when $P>k/n>P'$. As Bob increases $n$, the probability that Alice receives a correct message increases and that Mallory receives a correct message decreases. This is because the mean of secret shares Alice and Bob get remains $P n$ and $P' n$ respectively, while the standard deviation drops as $n$ increases.

But there is more than one way to do this. For example, Bob and Alice could choose a relatively small $n$, transfer TWO secrets s.t. their XOR is the original secret. In this case Mallory's probability of learning the original secret will be squared, and decrease much faster than Alice's.

So my question is: Is 'classic' secret sharing ALWAYS the best way (giving the smallest possible $n$ for a given $P$ and $P'$)? I could not find a counter-example yet.

• Just a correction: "Bob receives a correct message decreases" in 2nd paragraph. I think you mean Mallory? – chazisop Jul 31 '11 at 13:06
• The assertion that As Bob increases $n$, the probability... that Mallory receives a correct message decreases is a bit confusing. Is it meant to read something like As Bob increases $k$ and $n$, keeping their proportion the same, the probability...? – Peter Taylor Aug 5 '11 at 12:42