1
$\begingroup$

my first question on here.

I've gone through some examples of Shamirs Secret Sharing Scheme, but I have 2 rather pressing doubts -

i. Why do we choose the co-efficients of the polynomial from the set {1,..., p-1}?

ii. Why should we have p (the choice of prime) > n (total number of parties involved in the secret sharing scheme). I am able to reason why p > k but not the above!

Thanks very much in advance.

$\endgroup$
3
$\begingroup$

You need a finite algebraic object, resulting in exact arithmetic and exact recovery of the secret. So infinite fields such as $\mathbb{C,~R}$ are not suitable.

Since the scheme is based on polynomial interpolation, you need two operations, i.e., a field. It can be a prime field $\mathbb{F}_p$ or an extension field $\mathbb{F}_{p^m}.$

Since each user is assigned their secret by specifying $y_i$ at point $x_i,$ you need at least $n+1$ points, the value at zero of the polynomial normally being used for specifying the secret.

$\endgroup$
  • $\begingroup$ thank you for your reply - I definitely agree that if the co-efficients are in $\mathbb{F}_p$ then we must have that p >n. However, the issue I have is that I can't reason why we can't have co-efficients outside $\mathbb{F}_p$ - I tried with the following example - (2,2) Sharing Scheme with S = 5 , p = 7 and f(x) = 5 - 13x. I am able to recover the polynomial as 5 + x which is congruent to the original polynomial (mod 7) BUT I am still able to recover the secret - Am i missing something else here? $\endgroup$ – Rahul Mathur Oct 24 '18 at 19:29

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.