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.


2 Answers 2


Is the running times of corresponding steps true?


  • 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$.


In this paper,section $1$ given that Shamir secret sharing scheme time complexity is $O(t log^2 t)$, where $t$ is threshold. Please review this question again

  • $\begingroup$ you can't give a link to something on YOUR drive, it won't work. Care to explain your answer? $\endgroup$
    – kodlu
    Jun 1, 2021 at 11:30
  • $\begingroup$ @kodlu , I am given link , please see it $\endgroup$
    – Natwar
    Jun 1, 2021 at 11:45
  • $\begingroup$ the link is behind a paywall so non IEEE subscribers cannot see it. can you put in some details in your answer please? $\endgroup$
    – kodlu
    Jun 1, 2021 at 11:56
  • $\begingroup$ chat.stackexchange.com/rooms/127789/crypto-ai $\endgroup$
    – hanugm
    Jul 22, 2021 at 0:12

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.