Additive Secret Sharing

Additive secret sharing is the simplest secret sharing scheme. It splits a secret into \(n\) shares such that all \(n\) shares are required for reconstruction (an $n$-out-of-\(n\) access structure). It requires only an abelian group \((\mathbb{G}, +)\) and achieves information-theoretic security.

Given a secret \(s \in \mathbb{G}\) and \(n\) parties, the dealer:

1. Samples \(s_1, \ldots, s_{n-1} \leftarrow{} \mathbb{G}\) uniformly at random.
2. Sets \(s_n = s - \sum_{i=1}^{n-1} s_i\).
3. Distributes share \(s_i\) to party \(i\).

Reconstruction. All \(n\) parties combine their shares: \(s = \sum_{i=1}^{n} s_i\).

Security. Any subset of at most \(n - 1\) shares is uniformly distributed over \(\mathbb{G}^{n-1}\) and independent of the secret \(s\). The security is information-theoretic: no computational assumptions are needed, and the guarantee holds against unbounded adversaries.

• Only requires an abelian group \((\mathbb{G}, +)\). No field structure is needed, unlike Shamir secret sharing [1] which relies on polynomial interpolation over a finite field.
• The group \(\mathbb{G}\) must be finite with \(|\mathbb{G}| \geq 2\) for non-trivial security.
• Additive secret sharing is a special case of Shamir secret sharing with threshold \(t = n\).
• The concept of secret sharing was introduced independently by Shamir [1] and Blakley [2]. The additive variant is folklore.
• Commonly used in two-party computation protocols (e.g., GMW [3], garbled circuits with secret-shared inputs) and as a building block in multi-party computation protocols such as BGW [4].