Secret-sharing scheme

From CRYPTUTOR

A secret-sharing scheme is a method for some secret data to be distributed among many parties in such a way that the secret cannot be reconstructed unless certain groups of parties collaborate.

[edit]

Definition

$\mathcal{A}$ is called an access structure over a set $S$ is a monotone subset of $2 S$ . That is, if

$Y \in \mathcal{A} \mbox{ and } Y \subseteq X \implies X \in \mathcal{A}$ .

Let $\mathcal{A}$ be an access structure over $\{1,\ldots, n\}$ . Let us call $X$ an authorized set if $X \in \mathcal{A}$ . A $\mathcal{A}$ -secret-sharing scheme consists of the following algorithms:

Distribution: A randomized algorithm which takes an input $x$ and outputs $\sigma_1, \ldots, \sigma_n$ . We refer to $σ i$ as the $i$ th party's share of $x$ . For $I \subseteq \{1, \ldots, n\}$ , we use $σ I$ to denote the sequence $(\sigma_i)_{i \in I}$ .
Reconstruction: An algorithm which takes a set $I$ , a list of shares $σ I$ and outputs a string $x$ if $I$ is an authorized set.

We require the following correctness and security guarantees:

For all authorized sets $I$ and all $\sigma_1, \ldots, \sigma_n \gets \mathsf{Distribute}(x)$ , we must have $\mathsf{Recombine}( I, \sigma_I ) = x$ .
For all non-authorized sets $I$ and all $x, x'$ , the following distributions are identical:

$\{ \sigma_I \}_{ \sigma_1, \ldots, \sigma_n \gets \mathsf{Distribute}(x)} \equiv \{ \sigma_I \}_{ \sigma_1, \ldots, \sigma_n \gets \mathsf{Distribute}(x')}$ .

That is, if $I$ is an authorized set, then recombining the shares of parties in $I$ results in the original secret $x$ . However, if it is not an authorized set, then these shares are distributed independently of the secret (i.e, they reveal no information about the secret).

[edit]

Threshold secret sharing

If $\mathcal{A}$ is all subsets of $S$ of size $\ge t$ , then we call the scheme a $(n, t)$ -threshold secret-sharing scheme.

[edit]

Shamir's construction

We can easily construct a $(n, t)$ -threshold scheme for $m$ -bit secrets:

Distribution: Given $x \in \{0,1\}^m$ , choose a random degree- $(t - 1)$ polynomial $p$ in the field $G F (2 m)$ , such that $p (0) = x$ . This can be done by simply choosing random values for the polynomial's remaining coefficients. Then the $i$ th share is $p (i)$ , for $i \in \{1,\ldots, n\}$ .

If $t$ or more points of the polynomial are known, then the polynomial (and thus the secret) can be reconstructed using Lagrange polynomial interpolation. However, any subset of less than $t$ points are distributed uniformly, independent of the secret.

Retrieved from "http://crypto.cs.uiuc.edu/wiki/index.php/Secret-sharing_scheme"

Category: Cryptographic constructs