Shamir's scheme ( Secret Sharing)

Time Complexity

$O(t^{2})$ for secret computation? (requires polynomial interpolation)

Space Complexity

$O({1})$ per person, $O(t^{2})$ to figure out secret? words

(Each person only needs to keep track of a single point (O(1) info); figuring out secret depends on polynomial interpolation algorithm)

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

Word RAM

Year

1979