<p>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. </p>

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

CC BY-SA 3.0
2011-08-01T03:40:02.447Z
2011-08-01T03:40:02.447Z
user6584
<p>In the absence of any messages inserted by Mallory, the accepted secret sharing technique uses the <a href="http://en.wikipedia.org/wiki/Diffie_hellman" rel="nofollow">diffie helman</a> 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.</p>

CC BY-SA 3.0
2011-07-30T14:31:11.483Z
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.
Roei Schus
CC BY-SA 3.0
2011-08-01T10:22:02.243Z
@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".
Artem Kaznatcheev
CC BY-SA 3.0
2011-08-05T09:05:08.873Z
Yes, sorry about that :)
Roei Schus
CC BY-SA 3.0
2011-07-30T13:50:17.927Z
2011-07-30T14:52:51.080Z
2011-07-30T14:52:51.080Z
ratchet freak
<p>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&#39;$.</p>

<p>Assuming $P&gt;P&#39;$, Bob can use $(n,k)$-secret sharing when $P&gt;k/n&gt;P&#39;$.
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&#39; n$ respectively, while the standard deviation drops as $n$ increases.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2011-07-31T13:06:01.663Z
Just a correction: "Bob receives a correct message decreases" in 2nd paragraph. I think you mean Mallory?
chazisop
CC BY-SA 3.0
2011-08-05T12:42:09.713Z
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
<cr.crypto-security><pr.probability>
Reducing $n$ in $(n,k)$ secret sharing while keeping it effective
Roei Schus
# Reducing $n$ in $(n,k)$ secret sharing while keeping it effective

(Asked by: username_0 on 2011-07-30)

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.

**Tags:** cr.crypto-security, pr.probability

> **Comments:**
> **username_1**: Just a correction: "Bob receives a correct message decreases" in 2nd paragraph. I think you mean Mallory?  
> **username_2**: 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...`?  

---

## 2 answers

### Answer by username_3 on 2011-08-01. Score: 4

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.


---

### Answer by username_4 on 2011-07-30. Score: 0

In the absence of any messages inserted by Mallory, the accepted secret sharing technique uses the [diffie helman](http://en.wikipedia.org/wiki/Diffie_hellman) 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.

> **Comments:**
> **username_0**: 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.  
> **username_5**: @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".  
> **username_0**: Yes, sorry about that :)  

---

