5
$\begingroup$

Is it possible to construct a $t$-out-of-$n$ secret sharing scheme over $\Bbb Z_2$?

Shamir Secret Sharing allows for an arbitrary threshold $t$ and an arbitrary number of participants $n$, but requires the field to have at least $n$ elements. Is there a similar construction that works over $\Bbb Z_2$?

Addendum

One approach could be to use Shamir SS over the finite field $\Bbb F_{2^{\log n}}$. Then, to share $x\in\Bbb Z_2$, this value is first embedded in this field and then it can be secret shared. However, this has an (apparently) innecessary overhead (even though it could be amortized if we share more than value)

|improve this question
$\endgroup$
  • $\begingroup$ Just to be clear: You want a $t$-out-of-$n$ threshold secret sharing scheme that shares a single secret bit? $\endgroup$ – SEJPM♦ Jul 17 '18 at 10:26
  • $\begingroup$ @SEJPM That would be desirable, but I would be surprised if that's possible. $\endgroup$ – Daniel Jul 17 '18 at 10:27
  • $\begingroup$ There's a natural injection of $\mathbb Z/2\mathbb Z$ into $\mathbb F_{2^n}$ for any $n$. What stops you from using that? $\endgroup$ – Squeamish Ossifrage Jul 17 '18 at 14:03
  • $\begingroup$ @SqueamishOssifrage That's precisely what I wrote in the addendum, and I also said there why I didn't like that solution. Regarding SEJPM's question and this solution, I don't expect a scheme whose shares are $1$-bit long, but at least with a size independent of the number of shares. $\endgroup$ – Daniel Jul 17 '18 at 14:05
  • $\begingroup$ Independent is of course impossible; if your shares are $k$ bits, you can't have more than $2^k$ of them. $\endgroup$ – fkraiem Jul 18 '18 at 16:30
6
$\begingroup$

The question does not ask specifically for being in Shamir. This is a very interesting question, and has been studied in depth, with Ronald Cramer leading the effort. I refer you to the paper Algebraic Geometric Secret Sharing Schemes and Secure Multi-Party Computations over Small Fields as a starting point in your research.

|improve this answer
$\endgroup$
  • $\begingroup$ Thanks! This is basically what I was looking for. I expected people to have studied this before. $\endgroup$ – Daniel Jul 18 '18 at 9:57
  • $\begingroup$ Very interesting. Can you expand on the answer a bit, for the non-expert readers (article paywalled) since the paper seems to propose a much broader primitive. How small a $q$ is actualy doable? Is $q=2,$ as the OP asked even possible? I also noted that the construction does not really give a threshold scheme, the genus seems to come into it. $\endgroup$ – kodlu Jul 20 '18 at 12:23
1
$\begingroup$

If you are going to use polynomial interpolation you need $\geq n+1$ distinct evaluation points in your field (for the secret plus the individual shares) to make the mapping from the polynomial coordinates to the shares one to one. Otherwise two different set of shares might represent the same polynomial, thus the the same secret.

Thus, a prime or composite field size $q$ such that $q\geq n+1$ is necessary. This will also preserve the "no leakage of information given less than $t$ shares" property.

There is no way to relax this in a significant manner and remain in the Shamir scheme where the size of secret is proportional to the logarithm of the number of users, $n.$

|improve this answer
$\endgroup$
  • $\begingroup$ Yes, that's clear. So the solution I'm looking for is inherently not based in interpolation. I think the question of achieving SS over small fields is interesting and possibly non-trivial, so I'm looking for references that address this (I would be surprised if no one has taken a look at this before) $\endgroup$ – Daniel Jul 18 '18 at 6: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.