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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Oct 24, 2018 at 19:29
  • $\begingroup$ If I have number outside finite field I could map to this field using mod operator I think $\endgroup$
    – Macko
    Commented Dec 16, 2021 at 21:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.