Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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:
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$.
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.
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:
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.
