# Running time of Shamir's secret sharing scheme

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.

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

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

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