2
$\begingroup$

Let $p>n$ be a prime number. The key steps in the $(t,n)$ Shamir's secret sharing is as follows:

Steps of dealer:

  1. Choosing $s \in \mathbb{Z}_p^*$

  2. Selecting $b_i \in \mathbb{Z}_p^*$ for polynomial $g(x)=s+\sum_{i=1}^{t-1}b_ix^{i}$

  3. Calculating $s_i=f(i) \mod p$ /* assume that $i$ is the participant $P_i's$ public id.*/

  4. Distributing shares accordingly.

Participants step:

  1. Applying Lagrange polynomial interpolation to get s.

Running time analysis:

Steps of dealer:

  1. $O(1)$

  2. $O(t)$

  3. $O(t)$

  4. $O(t)$

Participants step:

  1. $O(t)$

Is the running times of corresponding steps true?

So, is overall time complexity $O(t)$?

I did not found any where over internet discussing running time of Shamir's secret sharing scheme. Is my analysis correct? Refer me any source or explain briefly the running times of steps involved.

$\endgroup$
6
$\begingroup$

Is the running times of corresponding steps true?

No.

  • Step 3 of the dealer has to be executed $n$ times (once for each party) with each execution taking $O(t)$ time. So it must be $O(t\cdot n)$.

  • Step 4 of the dealer needs $O(n)$ to distribute each share to every party.

I count $O(t\cdot n)$ as the overall time complexity for the dealer. Of course, you can make it more specific, because the time of all calculations depends on the size of $p$.

$\endgroup$

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.