2
$\begingroup$

How would we go about building a scheme for Shamir secret sharing for vectors? I have already tried to use a vector of secrets and random distribution of the secrets to $n$ parties and then use $t$ of them to get the data, where $t<n$.

$\endgroup$
  • $\begingroup$ Just do secret-sharing on some unique encoding in bits? $\endgroup$ – Squeamish Ossifrage Apr 25 at 1:38
3
$\begingroup$

To share a vector using Shamir's secret sharing, you can just share each element of the vector independently. It really is that simple.

To save some space, you can assign all the shareholders a distinct fixed non-zero $x$ coordinate and reuse those same $x$ coordinates for all elements of the vector being shared. The $x$ coordinates only need to be distinct; they don't have to be random or secret in any way.

(If your shareholders already have some unique ID that can be encoded as an element of the field you're using for Shamir's scheme, you could just use those as the $x$ coordinates. Or, if you're working in a sufficiently large field to make collisions unlikely — say, ${\rm GF}(2^{128})$ or larger — you could even derive the $x$ coordinate of each participant by hashing some arbitrary pre-existing public ID, like, say, an e-mail address. Just make sure not to allow $x = 0$ in any case, since that directly leaks the secret.)

In fact, the only reason we don't just interpret all secrets as vectors of bits and run Shamir's scheme over ${\rm GF}(2)$ is the fact that the field size limits the number of shareholders (and, in particular, a two-element field allows only one shareholder, which is kind of useless). However, it is quite common to e.g. interpret arbitrary strings as vectors of 8-bit bytes, and share them with Shamir's scheme over ${\rm GF}(2^8)$, which works for up to 255 shareholders.

$\endgroup$
2
$\begingroup$

As already pointed out in the comments there is nothing special about a vector, right? So you could just transform it to some binary representation and use Shamir secret sharing to distribute the shares among the shareholders.

If you say each component of your vector is viewed as a secret you could use multiple applications of the secret sharing protocol. However, if you distributing them to the same shareholders I think you won't gain any benefits regarding security in contrast to just use the whole vector as a single secret.

$\endgroup$
  • $\begingroup$ If the vector is very long, there might be some practical efficiency gains to be made by not having to do arithmetic in a huge finite field. But I do agree that your method is perfectly fine and usable. $\endgroup$ – Ilmari Karonen Apr 25 at 8:48
  • $\begingroup$ Good point! However, do you think that the gains in efficiency by not having to do arithmetic in huge finite fields outweighs the added communication overhead resulting from multiple executions of the protocol? $\endgroup$ – grees Apr 25 at 9:11
  • $\begingroup$ There is no significant (necessary) overhead either way: you're transmitting the same amount of data regardless of whether you send $k$ small shares or one big share that's $k$ times the size. As I note in my answer, the $x$ coordinates of the shares need to be sent (at most) once anyway, since they can be reused, and they can be chosen to be small even if the field is large. Of course, there may also be some overhead if the field size you're using doesn't exactly match the space your secrets are chosen from; but that can go either way. $\endgroup$ – Ilmari Karonen Apr 25 at 9:26

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.