patternMinor
Condition in Shamir Secret Sharing Scheme
Viewed 0 times
schemeconditionsecretshamirsharing
Problem
For Shamir's secret sharing scheme (doi 10.1145/359168.359176), one obtains a random polynomial $q$ of degree at most $n-1$ (over $\mathbb{Z}_p[x]$). The constant coefficient of this polynomial is defined to be the key. Then the scheme sends to player $i$ the value $q(i)$ (for $i \leq k$ for some fixed $k$). The interpolation theorem says that if $n$ players come together, then I can use interpolation to reconstruct the polynomial (there is a unique polynomial $p$ of degree at most $n-1$ such that $p(i)=q(i)$ .. in otherwords $p=q$. So that I can grab the constant coefficient of $p$ and it must be the same as the constant coefficient of $q$, and hence must be the key).
The question I have, is that what if the polynomial is degree less than $n-1$. There seems to be nothing in the construction as described by Shamir that prevents this. However, Shamir states that $n-1$ players cannot reconstruct the polynomial.
The problem I am having is that there seems to be a "most of the time" clause missing. If I happen to pick a degree one polynomial then any two players can reconstruct the polynomial. So is it that the players do not know the degree of the polynomial, or that the probability of picking a small degree polynomial is low enough that the probability of two participants guessing the key is still the same as random guessing, or am I missing something else.
The question I have, is that what if the polynomial is degree less than $n-1$. There seems to be nothing in the construction as described by Shamir that prevents this. However, Shamir states that $n-1$ players cannot reconstruct the polynomial.
The problem I am having is that there seems to be a "most of the time" clause missing. If I happen to pick a degree one polynomial then any two players can reconstruct the polynomial. So is it that the players do not know the degree of the polynomial, or that the probability of picking a small degree polynomial is low enough that the probability of two participants guessing the key is still the same as random guessing, or am I missing something else.
Solution
I am not sure if this will completely answer the question, but I have a couple observations that might help.
First, note that for the random polynomial $q$, $q(0) = a_0$ is the key -- this is from the way that polynomial interpolation works. So it is important that the value $q(0)$ is never sent to a participant; $q(i)$ is sent for $0 k$ (where $k$ is the number of participants) -- it is to ensure that I can obtain $k$ "shares" without revealing the key.
Second, the polynomial $q$ is not just random, but also secret. The fact that the degree of the polynomial $q$ is unknown matters. When $n-1$ participants come together, they can do anything they want -- they are super clever. They claim that the key is $w$. However, there is a unique polynomial $g$ of degree $n-1$ such that
$$g(i) = q(i)$$
and
$$g(0) = w$$
However, this would be true for any $w$. Since we know that the secret is given by a polynomial of degree less than $n$, and from the data that the pool of $n-1$ participants have, any value of key supposed is as likely ... no value of key can be ruled out.
**Note however, that this is not true if the participants know the degree of the polynomial.
First, note that for the random polynomial $q$, $q(0) = a_0$ is the key -- this is from the way that polynomial interpolation works. So it is important that the value $q(0)$ is never sent to a participant; $q(i)$ is sent for $0 k$ (where $k$ is the number of participants) -- it is to ensure that I can obtain $k$ "shares" without revealing the key.
Second, the polynomial $q$ is not just random, but also secret. The fact that the degree of the polynomial $q$ is unknown matters. When $n-1$ participants come together, they can do anything they want -- they are super clever. They claim that the key is $w$. However, there is a unique polynomial $g$ of degree $n-1$ such that
$$g(i) = q(i)$$
and
$$g(0) = w$$
However, this would be true for any $w$. Since we know that the secret is given by a polynomial of degree less than $n$, and from the data that the pool of $n-1$ participants have, any value of key supposed is as likely ... no value of key can be ruled out.
**Note however, that this is not true if the participants know the degree of the polynomial.
Context
StackExchange Computer Science Q#6981, answer score: 4
Revisions (0)
No revisions yet.