Is there an efficient 2 out of 3 secret sharing scheme based on XOR?

Question

I want to know if there is an efficient secret sharing scheme based on XOR such that a share of the message is given to three people and at least two must combine their share in order to construct the message?

What I have tried so far:

Suppose I got a message $M$, and three people A, B and C. Then what I do is

• A gets $a_1 = M \oplus \alpha$ and $a_2 = \beta$
• B gets $b_1 = M \oplus \beta$ and $b_2 = \alpha$
• C gets $c_1 = \alpha$ and $c_2 = \beta$

Where $\alpha$ and $\beta$ are two randomly generated bits the size of the message.

This works fine (with some modification), but the problem is that each person have to store twice the size of the message. Is there a more efficient one?

Answer 1

Let's say the message is $\ell$ bits long, and we'll work in the Galois field $\operatorname{GF}(2^\ell)$ where addition is xor. If Alice, Bob, and Charlie agree in advance on a generator $\alpha \in \operatorname{GF}(2^\ell)$ (or at least an element of order greater than 3), then we can pick $u$ uniformly at random and assign them the shares $(1, m + u \alpha)$, $(2, m + u \alpha^2)$, and $(3, m + u \alpha^3)$. That is, each party stores $(i, f(\alpha^i))$ where $f(x) = m + u x$; given two shares $s_i = m + u \alpha^i$ and $s_j = m + u \alpha^j$ for $i \ne j$, it is easy to recover $$m = s_i - \frac{s_i - s_j}{\alpha^i - \alpha^j} \alpha^i = s_j - \frac{s_i - s_j}{\alpha^i - \alpha^j} \alpha^j$$ from the two points on the line $f$.

This is Shamir's 2-of-3 secret-sharing scheme[1] (paywall-free). The per-party storage is a small integer plus an $\ell$-bit share. Of course the parties all have to agree in advance on the generator $\alpha$, but they also have to agree on the rest of the computation anyway. In general, the per-party storage cost for Shamir's $t$-of-$n$ secret-sharing scheme is $\ell + \lceil\log_2 t\rceil$. This cost is near the information-theoretic lower bound of $\ell$ bits.

But we could use cryptography to get a lower cost. To wit[2]:

1. Encrypt the message $m$ under secret key $k$ giving ciphertext $c$.
2. Split the ciphertext into shares $c_1, c_2, \dots, c_n$ of which any $t$ suffice to reconstruct $c$ using erasure coding, like Reed–Solomon codes or Rabin's information dispersal algorithm, which is efficient but doesn't conceal anything from an adversary.
3. Split the key into shares $k_1, k_2, \dots, k_n$ of which any $t$ suffice to reconstruct $k$ using secret sharing, like Shamir's secret-sharing scheme, which is inefficient but conceals the key from any adversary with fewer than $t$ shares.

If the ciphertext is $\ell$ bits long (accounting for possible ciphertext expansion if you sign it to thwart malicious parties corrupting their shares) and the key is $\lambda$ bits long, the per-party storage is $\ell - \lfloor\log_2 t\rfloor + \lambda$ bits. We save space by splitting the message among multiple parties with erasure coding instead of secret-sharing, but we have to make up for it by doing secret-sharing on a secret key.

Finally, note that secret-sharing always poses a practical problem: when you first construct the shares, the dealer has to have the whole secret in one place to begin with, and every time you want to reconstruct the shares, the party acting on the reconstruction always has to have the whole secret in one place. Many applications are better served by multiparty computations like threshold signatures, where no party unilaterally has access to the whole secret at any time.

Answer 2

Here is a simple (2, 3) secret sharing scheme that used only xor's, and each share is the same size as the secret (assuming that the secret is an even number of bits long)

First, we divide the secret $s$ into two equal sized halves, $s_1, s_2$.

And, we pick two random values of the same size, $r_1, r_2$

Then, the Alice shares are $a_1 = s_1 \oplus r_1$, $a_2 = s_2 \oplus r_2$

The Bob shares are $b_1 = s_1 \oplus r_2$, $b_2 = s_2 \oplus r_1 \oplus r_2$

And the Carol shares are $c_1 = s_1 \oplus r_1 \oplus r_2$, $c_2 = s_2 \oplus r_1$.

It is straight-forward to show that any two parties can recover the secrets $s_1, s_2$

With the Alice and Bob shares, we have $s_1 = a_1 \oplus a_2 \oplus b_2$, $s_2 = a_1 \oplus b_1 \oplus b_2$

With the Alice and Carol shares, we have $s_1 = a_2 \oplus c_1 \oplus c_2$, $s_2 = a_1 \oplus a_2 \oplus c_1$

With the Bob and Carl shares, we have $s_1 = b_1 \oplus b_2 \oplus c_2$, $s_2 = b_1 \oplus c_1 \oplus c_2$

And, with a single share, neither Alice nor Bob nor Carol gain any information about the value of the secret (assuming $r_1, r_2$ was picked randomly).

And, if the total length of the secret is n bits (and so each half of the secret is $\lceil n/2 \rceil$ bits long), the total length of each share is $2 \lceil n/2 \rceil$ bits, which is $n$ bits if $n$ is even.