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.

  • $\begingroup$ For the bit on modular arithmetic and the need for a prime (or some integer of the form p ^ k where p is prime), I referred to the example on Wikipedia and constructed some of my own arguments - en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing $\endgroup$ – Rahul Mathur Oct 22 '18 at 17:40

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.

  • 1
    $\begingroup$ Thanks very much Ken, appreciate your answer along with the example provided! $\endgroup$ – Rahul Mathur Oct 22 '18 at 17:39

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.

  • $\begingroup$ Thanks very much for your answer - so my hunch has been confirmed - the idea is that the phrase "no leak of information" from this secret sharing scheme means that you cannot gain any further information other than it is in the set {0,...., (p-1)}. Much appreciated! $\endgroup$ – Rahul Mathur Oct 22 '18 at 17:35

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.