Necessity for finite field arithmetic and the prime number p in Shamir's Secret Sharing Scheme

Question

Shamir's original paper (PDF, 197kb) describing a threshold secret sharing scheme states:

To make this claim more precise, we use modular arithmetic instead of real arithmetic. The set of integers modulo a prime number $p$ forms a field in which interpolation is possible. Given an integer valued data $D$, we pick a prime $p$ which is bigger than both $D$ and $n$. The coefficients $a_1,...,a_{k-1}~$ in $q(x)$ are randomly chosen from a uniform distribution over the integers in [0, $p$), and the values $D_1,...,D_n$ are computed modulo $p$.

Where:

• $D$ is the secret to be shared
• $n$ is the number of shares
• $k$ is the threshold number of shares needed to reconstruct $D$
• $q(x)$ is a $k-1$ order polynomial with $q(0)=D$ and the coefficients $a_1,...,a_{k-1}~$
• $D_1,...,D_n$ are individual shares (points on the polynomial $q(x)$)

Can someone please explain (in the simplest possible manner) the reason that Shamir's Secret Sharing Scheme uses finite field arithmetic? Also, why must the size of the Galois field be a prime number with the requirements that Shamir put forth?

The reason for asking these questions is: I would like to implement Shamir Sharing in Javascript using a field of size $2^8 = 256$, which:

1. will obviate the need for a big integer library for Javascript, such as jsbn
2. will simplify the math.

Whatever the size of the secret to be shared, it could be broken down into byte-length segments and the math performed on those segments. The resulting share would be a concatenation of the results of the necessary operations on each segment.

To find the secret, the shares can again be broken down into byte-length segments. The polynomial interpolation can be done with the corresponding byte-length segments from the shares to get individual segments of the secret. The segments can then be concatenated to form the complete secret.

Would this work and be cryptographically secure?

If there is indeed an absolute necessity for a prime number $p$, could I use any small prime number with the concatenations described to perform the necessary operations in Javascript and still remain cryptographically secure?

Answer 1

There is no reason in Shamir's scheme for the finite field $\mathbb F$ to have a prime number $p$ of elements; the field can have $p^m$ elements for suitable prime $p$ and integer $m \geq 1$. So, using $F_{2^8}$, the field with $2^8$ elements is perfectly all right. However, choosing $m = 1$ has the advantage that calculations in $\mathbb F_p$ can be done using the standard arithmetic unit included in microprocessors and the like (followed by integer divisions for doing the mod $p$ operations) whereas using $\mathbb F_{p^m}$ requires having a library already available (or developing one) or building a processor for arithmetic in the field.

Given that you have the capability of doing arithmetic in $\mathbb F_{2^8}$, you can use this field if you like. But, (as you say) in Shamir's scheme, the secret is just one element of the field (one $8$-bit byte), and so, if the Secret to be shared is several bytes long, you will need to process each byte separately into its (one-byte) shares, and concatenate the $i$-th share bytes into the $i$-th Share of the Secret. Keep in mind that each byte can be divided into at most $255$ shares (the point $q(0)$ on $q(x)$ cannot be used for obvious reasons), and so if you need to have more than $255$ shares to distribute, you will have to use a different field. Finally, to maintain cryptographic security, as the shares corresponding to each byte of the Secret are being computed, you should do exactly what you say you are doing in your comment: use a different set of "randomly chosen coefficients" for $q(x)$, rather than re-use the same set over and over again for finding the shares of all the bytes.