Secret Sharing

Description

Secret Sharing is the splitting up of a secret amongst a group such that no individual can learn the entire secret alone, but when a sufficient amount of the group comes together with their parts of the secret, they can reconstruct the secret.

Parameters

$n$: size of the group the secret is being shared with

$t$: threshold number of players

Table of Algorithms

Name	Year	Time	Space	Approximation Factor	Model	Reference
Shamir's scheme	1979	$O(t^{2})$ for secret computation? (requires polynomial interpolation)	$O({1})$ per person, $O(t^{2})$ to figure out secret?	Exact	Deterministic
Blakley's scheme	1979	$O(t^{3})$ for secret computation? (requires linear solver)	$O(t)$ per person, $O(t^{2})$ to figure out secret	Exact	Deterministic