2
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Just a correction: "Bob receives a correct message decreases" in 2nd paragraph. I think you mean Mallory? $\endgroup$
    – chazisop
    Jul 31, 2011 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, 2011 at 12:42

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 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, 2011 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, 2011 at 10:22
  • $\begingroup$ Yes, sorry about that :) $\endgroup$
    – Roei Schus
    Aug 5, 2011 at 9:05

Your Answer

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

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