Shamir Secret Sharing Scheme - leak of information

Question

After going through some literature, I've convinced myself that to recover the exact secret using Shamirs Secret Sharing scheme, we must have S(the secret converted into a number) < p (choice of prime) and n (total number of parties) < p.

I understand that the reason for incorporating modular arithmetic and the prime p is to ensure that there isn't any leak of information. However, since the prime p is a public number, isn't there anyways a leak of information that the secret S < p? (i.e. not all real numbers have the same probability of being S)

Thanks very much in advance.

Answer 1

Since all the operations are with respect to the field defined by $p$, for a threshold of $t$ shares required for reconstructing the secret, any set of $t-1$ shares reveals no information about the secret, even in a probabilistic sense. This is the claim given in the original presentation of Shamir's scheme, and is in fact true due to the properties of finite groups and polynomial interpolation within them.

For a brief but illustrative example, consider the polynomial $4x^2+3x+1\in\mathbb{Z}_5$ to keep things reasonably small for a manual example. If we have three parties involved in the scheme, given two of their shares we should not be able to gain any information with respect to the secret, 1. If it is known that the shares of $P_1$ and $P_2$ are both $3$, for example, what information has been gained about the secret? Since the polynomial is of degree 2, 3 points are minimally required for using interpolation to identify the unique polynomial fitting the points. In this example it is easy to see that if the share of $P_3$ is 0 the secret revealed will be 4, and every other domain value results in a different secret value being revealed all solely dependent on the share of player three when shares for players 1 and 2 are known and fixed. Explicitly and exhaustively, given a list of potential share values for $P_3$ $[0,1,2,3,4]$ across the whole domain of possibilities, the resulting secrets revealed using this combination are $[4,0,1,2,3]$ respectively, and with equal probability since the share of $P_3$ is uniformly random. This is, once again the whole domain of possibilities and all are equally likely.

Therefore the scheme is information theoretically secure, because the property demonstrated in this brief and small example holds with respect to every combination of every proper subset of shares less than the threshold and every field of prime order, assuming of course that the scheme was set up correctly with appropriate parameters.

Answer 2

You are correct that the secret needs to be an integer between 0 and $p-1$. It cannot be a fraction and cannot be a real number (that's not an integer). Thus, what Shamir's secret sharing scheme actually guarantees is that (unless you have a quorum of shares) you have no information about which of the values in the set $\{0,1,...,p-1\}$ the secret is. However, in cryptography, (essentially) everything is in a finite set (albeit a large finite set). Thus, hiding it in this way suffices.