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?
1 Answer
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.$