5
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Shirley you need another couple of bits to distinguish the users, no? $\endgroup$ – Squeamish Ossifrage Mar 31 at 19:01
  • $\begingroup$ @SqueamishOssifrage: I thought those sorts of public identifiers weren't counted as part of the secret share size. I don't call me Shirley :-) $\endgroup$ – poncho Mar 31 at 19:03
  • $\begingroup$ Well, I guess they need not be secret, but one does need to store them. $\endgroup$ – Squeamish Ossifrage Mar 31 at 19:04
  • 1
    $\begingroup$ @IlmariKaronen: awww, you gave the secret away (and, yes, that is how I found it...). And, so, yes, it generalizes to a $(t, n)$ sharing scheme, where you end up dividing the secret into $\max( t, \log_2(n+1) )$ parts... $\endgroup$ – poncho Apr 1 at 11:31
  • 1
    $\begingroup$ @poncho The secret was not given away! Now it's a shared secret :D $\endgroup$ – Daniel Apr 8 at 13:27
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What about a $t$ out of $n$ secret sharing scheme that allows to distribute one bit with the share-length being also one bit? (in a non-amortized setting). $\endgroup$ – Daniel Mar 30 at 23:15
  • 1
    $\begingroup$ It seems unlikely that you can do better than two bits per party. You'd have to find boolean dealer functions $f_1$, $f_2$, $f_3$ such that $f_i(m, u) \oplus f_j(m, u) = m$ for any $i \ne j$ but $P(m \mid f_i(m, u)) = P(m)$ for all $i$, where $u$ is a dealer secret with some distribution. (The recombining function has to be a nontrivial commutative boolean function since the parties can't even store which party they are, so it's either EQV or XOR.) I conjecture that this is impossible. Proof or counterexample left as exercise for reader. $\endgroup$ – Squeamish Ossifrage Mar 31 at 0:30
  • $\begingroup$ That doesn't address the question. I wanted Xor based secret sharing!! $\endgroup$ – Baby desta Mar 31 at 15:19
  • $\begingroup$ In $\operatorname{GF}(2^\ell)$, $+$ is xor. $\endgroup$ – Squeamish Ossifrage Mar 31 at 15:53
  • $\begingroup$ @SqueamishOssifrage , thank you for the extended explanation. I appreciate it. $\endgroup$ – Baby desta Apr 12 at 13:56

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.