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.

  • 2
    $\begingroup$ Just a correction: "Bob receives a correct message decreases" in 2nd paragraph. I think you mean Mallory? $\endgroup$ – chazisop Jul 31 '11 at 13:06
  • $\begingroup$ 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...? $\endgroup$ – Peter Taylor Aug 5 '11 at 12:42

This sounds related to Wyner's "wiretap channel": Wyner showed that an asymmetry between receiver and eavesdropper could be used to achieve information-theoretic security. There have been many, many follow-up works since then.

Reference: A. D. Wyner, The wire-tap channel. Bell Sys. Tech. J., vol. 54, pp. 1355-1387, 1975.


In the absence of any messages inserted by Mallory, the accepted secret sharing technique uses the diffie helman exchange (even if Mallory got all messages she wouldn't be able to get the secret). This relies on discrete logarithms being hard to compute.

  • 3
    $\begingroup$ Thank you, but Diffie-Hellman has one property which makes it irrelevant: It demands a two-sided communication channel - that is not the model I have presented. $\endgroup$ – Roei Schus Jul 30 '11 at 14:31
  • 3
    $\begingroup$ @roei can you explicitly include in the question that you are looking for one-sided communication channels by saying something like "he can only send messages using a one-sided channel which is insecure and unreliable"? Just to protect against people like me that read the post and assumed "and Alice can do the same thing as Bob". $\endgroup$ – Artem Kaznatcheev Aug 1 '11 at 10:22
  • $\begingroup$ Yes, sorry about that :) $\endgroup$ – Roei Schus Aug 5 '11 at 9:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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