5
$\begingroup$

Does the prime (which needs to be larger than the message) have to be chosen randomly for security, or can it just be a huge constant?

Also, the Wikipedia article for SSSS states

The size of each share does not exceed the size of the original data.

but isn't each share comprised of both $X$ and $Y$? or is $X$ already known because of the prime? and if the prime is chosen at random then surely the prime has to be distributed with each share?

$\endgroup$
5
  • $\begingroup$ The prime does not even need to be large, 13 provides as much security as some 1024 bit prime. It just can share as large of secrets or be split into as many shares. $\endgroup$
    – mikeazo
    Sep 14, 2016 at 10:45
  • $\begingroup$ mikeazo "the prime does not even need to be large"?? maybe it doesn't need to be huge but it does need to be greater than the message $\endgroup$
    – David
    Sep 15, 2016 at 2:57
  • 1
    $\begingroup$ Actually, because you can split up the message into parts (and separately share each part), the prime needn't be as big as the message. $\endgroup$
    – poncho
    Sep 15, 2016 at 16:19
  • $\begingroup$ @poncho In that case dont you essentially just get a new secret sharing where each share is a bunch of small shares which add up to the size of secret? $\endgroup$
    – Guut Boy
    Sep 16, 2016 at 7:25
  • $\begingroup$ @GuutBoy: true, but it does show that the size of $P$ needn't be as large as the secret. If you're sharing a 256 bit AES key, you don't need a 256+ bit prime (or, more precisely, field size; since SSS works in Galois (extension) fields, well, you never need a prime larger than 2 anyways...) $\endgroup$
    – poncho
    Sep 16, 2016 at 12:47

2 Answers 2

6
$\begingroup$

The prime can be just any prime, so it doesn't have to be chosen randomly (but of course it can). And the prime is made public, so it is not part of the shares. Public values are known by definition by everyone, therefore are not part of the shares.

But you're right, the quote is wrong about the size of the share, because it neglects $x$. However, it's really close, because $y$ is usually the same length as $p$ (uniform distributed), but $x$ can be chosen to be small.

$\endgroup$
6
  • $\begingroup$ is it ok if a program constantly uses one hard-coded large prime to cater for say all <128bit messages, or is it also important to use different primes with each secret message? thankyou again for clarifying!!!:) $\endgroup$
    – David
    Sep 16, 2016 at 6:59
  • 1
    $\begingroup$ @David: of course that'd be fine; assuming that you're OK with leaking whether the message is < 128 bits. And, you don't need to use a different prime for each message. BTW: one thing that's common practice is SSS is to do the work in a $GF(2^{8x})$ field; the math isn't difficult, it's just as secure, and everything nicely fits in even-byte quantities... $\endgroup$
    – poncho
    Sep 16, 2016 at 13:07
  • 2
    $\begingroup$ @David: what's absolutely critical is that you never reuse the secret polynomial; it needs to be generated randomly every time you create a set of shares. Everything else, the $x$ coordinates, the value $p$ (or the field size, if you take my suggestion of $GF(2^{8x})$), can be reused between different sets of shares $\endgroup$
    – poncho
    Sep 16, 2016 at 13:09
  • 1
    $\begingroup$ The prime (or, more generally, the order of the finite field) does need to be greater than the number of shares, so just any prime won't do. For example, the prime $2$ would generally be a poor choice. ;) $\endgroup$ Sep 17, 2016 at 20:37
  • $\begingroup$ are huge integers required for security? $\endgroup$
    – David
    Sep 18, 2016 at 15:01
5
$\begingroup$

Shamir's secret sharing can be done over any finite field. While fields of prime order are somewhat simpler to understand for many people, since arithmetic in them is simply ordinary addition and multiplication modulo a prime, for practical applications of Shamir's scheme it is often convenient to use a field of order $2^k$ for some integer $k$, since elements of such fields can be easily represented as $k$-bit bitstrings (and vice versa, any $k$-bit string can be represented as a number in a finite field of order $2^k$).

In any case, the order of the field (and any other aspects of it, like the reduction polynomial for non-prime fields) are public parameters of the scheme, and do not need to be secret. Indeed, to be able to reconstruct the secret, all participants of the scheme must know what the field is and how it's represented.

While the field used for Shamir's secret sharing can in principle be chosen arbitrarily, there do exist some practical constraints on its size. Most notably:

  1. The maximum number of shares the secret can be split into is one less than the order of the field. That's because each participant's share is given by evaluating the polynomial at a distinct point $x$ (and the secret itself is given by the value of the polynomial at yet another point, conventionally $0$), and there are only $n$ points in a finite field of order $n$.

  2. The secret must be representable as an element of the field, and thus must be less than the order of the field. In practice, this is not a serious issue, since long secrets can simply be split into smaller chunks that do fit in the field, with each chunk shared separately.

  3. The generated shares are effectively random elements of the field. Thus, using an unnecessarily large field leads to unnecessarily large shares.

For example, using the finite field $GF(2^8)$, we can simply split the message to be shared into 8-bit bytes and apply Shamir's secret sharing to each byte separately, with the shares also being single bytes. However, using this field, we can only share the message among at most $255$ participants, since there are only $2^8 = 256$ elements in the field, and one of them is needed for the secret.

On the other hand, using the field $GF(2^{256})$ would let us generate up to $2^{256}-1$ shares, i.e. way more than we could possibly ever need. However, each of these shares would be $256$ bits long, even if the secret was known to be much shorter than that.

Also, if we didn't like implementing finite field multiplication in $GF(2^8)$, we could use e.g. the prime-order field $GF(257)$ instead, and just work with ordinary multiplication and addition modulo $257$. But now, even though all bytes can still be represented as field elements, we now also have an extra field element, $256$, that does not fit into an 8-bit byte. Thus, we'd need to come up with some encoding scheme for our shares that lets us represent all the field elements from $0$ to $256$ inclusive.

As for the size of the shares, the conventional way is to only count the value of the polynomial $y = f(x)$ as the share, and to ignore the point $x$ itself. Of course, to reconstruct the secret, we do need to know the points $x$ too, but:

  1. the points at which the polynomial is evaluated do not need to be secret,
  2. the same points can be reused for sharing multiple secrets among the same participants, and
  3. often, it's possible to choose the points based on some kind of IDs that the participants already have, so that they don't need to be stored separately at all.

So, for example, if we wanted to share an $n$-byte message using the field $GF(2^8)$, then each participant in the scheme would typically receive one byte representing the point $x$, plus $n$ bytes $y_1 = f_1(x)$, $y_1 = f_2(x)$, …, $y_n = f_n(x)$ corresponding to their shares of each byte of the message. Thus, regardless of the length of the message, the complete shares would only be one byte longer than the message.

Alternatively, if we were using Shamir's secret sharing over a larger field, like $GF(2^{256})$, then we could simply choose each participant's point $x$ as e.g. the SHA-256 hash of their e-mail address (or whatever other unique ID we might be using to identify them). As long as the number of participants remained much smaller than the square root of the field order, the chances of two $x$ values computed in this way colliding will be negligibly small. In this way, the participants would not need to store their $x$ values at all, since they could always just recompute them as needed.

Of course, in either case, the participants would also need to know how the shares need to be combined, i.e. what field to use, with which reduction polynomial if any, and so on. If such meta-information may vary, it may also need to be stored alongside the shares in order to allow the secret to be reconstructed. But, again, this information does not need to be kept secret, so it's fine to store it in a public place. And, again, it only represents a constant overhead.

$\endgroup$
3
  • $\begingroup$ This is literally the only correct answer here. The size of the modulus does matter for security, because it is the upper bound of the secret key. You cannot recover a 256-bit key when using a modulus of 13. $\endgroup$ Nov 29, 2022 at 15:35
  • $\begingroup$ @TylerPantuso: …but you could encode a 256-bit key as 70 base-13 digits and shared those using Shamir's secret sharing over $GF(13)$ if you wanted to; the resulting 70 base-13 shares could then be converted back into binary as one 260-bit share. With 263 bits (which is still less than one extra byte compared to the original 256-bit key) you could even fit in the base-13 $x$ coordinate, too. Of course, the biggest drawback of this scheme (as opposed to, say, using $GF(2^8)$) is that you could only have at most 12 shares. $\endgroup$ Nov 30, 2022 at 16:08
  • $\begingroup$ Sounds interesting. Kind of reminds me of a paper from IBM called "Secret Sharing Made Short" (Krawczyk, 1998). Except they use a secret sharing scheme to share a symmetric key. Kind of the same concept though, where the size of each share = size of the secret / number of shares. $\endgroup$ Nov 30, 2022 at 20:13

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.