Skip to main content
edited body
Source Link
Ken Goss
  • 701
  • 5
  • 11

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 2 and 4 respectivelyboth $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.

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 2 and 4 respectively, 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.

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.

added 199 characters in body
Source Link
Ken Goss
  • 701
  • 5
  • 11

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 2 and 4 respectively, 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.

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 2 and 4 respectively, 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.

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 2 and 4 respectively, 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.

Source Link
Ken Goss
  • 701
  • 5
  • 11

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 2 and 4 respectively, 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.