0
$\begingroup$

Hi this is for the Shamir Secret Sharing algorithm.

How do I create a polynomial of degree k-1 such that P(0) = s (mod m).

where k-1 is just an integer, s is just an integer, m is a large prime.

2 Answers 2

2

It is rather important to pick a polynomial satisfying the given condition randomly for the algorithm to work. Since the polynomial is then used to calculate the different $s_i = f(i) \mod m$ for the different shares.

In particular, choosing a random polynomial f over $Z_m$ of degree k-1 satisfying f(0) = s is equivalent to choosing $a_1, \dots, a_{k-1} \in \mathbb{Z}_m$ at random, with $a_{k-1}\neq 0 \mod m$ and letting f(x) be the polynomial $f(x) = s+a_1x+a_2x^2+\dots+a_{k-1}x^{k-1}$.

  • 1
    if a_{k-1} were equal to 0 break the algorithm or just make cracking this particular f(x) easier?2011-07-11
  • 1
    Originally, the scheme proposed in Shamir's paper http://securespeech.cs.cmu.edu/reports/shamirturing.pdf used a polynomial of fixed degree. However, requiring degree *at most* k-1 would still work, since with the given points, Lagrange interpolation will recover a unique polynomial of degree at most k-1, see for example Proposition 1 in http://www.daimi.au.dk/~ivan/SecretSharing.pdf2011-07-11
  • 0
    So then cracking f(x) would become easier, is what you're saying right? The term "easier" meaning less possibilities to brute force.2011-07-11
  • 0
    To the contrary, it still works. Please read the second article I cited.2011-07-11
1

Am I missing something?

$p(x)=x^{k-1}+s$?

  • 0
    oh..........wow. is that how the shamir secret sharing algorithm is expecting people to create such a random k-1? basically just have the s be a constant at the end???2011-07-11
  • 0
    idk, i may just have been overthinking it!2011-07-11
  • 0
    I am not familiar with the algoritm, so I do not know how the polynomials pop-up there. Maybe there are other constraints?2011-07-11