Running time of Shamir's secret sharing scheme

Question

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.

Answer 1

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

Answer 2

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