3
$\begingroup$

confused about differences between 5 out of 5 threshold secret sharing scheme and 4 out of 5 threshold secret sharing scheme. how would the share and reconstruction schemes be different assuming both of them use xor?

$\endgroup$
1

1 Answer 1

2
$\begingroup$

For $(t,n)$ where $t=n,$ and where the secret is the vector $Z,$ the XOR based scheme is:

Scheme $\cal S:$

  • distribute $n$ shares, one to each user, as the binary vectors $$S_1=X_1,S=2X_2,\ldots,S_{n-1}=X_{n-1},S_n=Z\oplus X_1\oplus \cdots\oplus X_{n-1}$$.
  • reconstruct $Z$ by computing $S_1\oplus\cdots S_n$.

For $t=n-1,$ one way is to create $n$ different $(n-1,n-1)$ schemes for each of the $n$ subsets of size $t=n-1$. So for the users $1,2,\ldots,n-1$ we can use the scheme

Scheme ${\cal S}(1,\ldots,n-1):$

  • distribute $n-1$ shares, one to each user, as the binary vectors $$S_1=X_1,S_2=X_2,\ldots,S_{n-2}=X_{n-2},S_{n-1}=Z\oplus X_1\oplus \cdots\oplus X_{n-2}$$.
  • these users reconstruct $Z$ by computing $S_1\oplus\cdots S_{n-1}$. .

Note that the sums of the different shares differ by the xor of two random vectors, in the symmetric difference of the two sets of users, and if these are uniformly generated the required intra-subset security property will hold.

Obviously this multiplies storage and communication by a factor of $n.$

$\endgroup$

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.