Shamir's secret sharing scheme [Sha79] is a threshold scheme based on polynomial interpolation. To allow any m out of n people to construct a given secret, an (m-1)-degree polynomial
f(x) = a0 + a1 x + ¼+ am-1 xm-1
over the finite field GF(q) is constructed such that the coefficient a0 is the secret and all other coefficients are random elements in the field; the field is known to all participants. Each of the n shares is a pair (xi, yi) of numbers satisfying f(xi) = yi and xi ¹ 0. Given any m shares, the polynomial is uniquely determined and hence the secret a0 can be computed. However, given m-1 or fewer shares, the secret can be any element in the field. Therefore, Shamir's scheme is a perfect secret sharing scheme (see Question 2.1.9).
Figure 3.1: Shamir's secret sharing scheme (click for a larger image)
A special case where m = 2 (that is, two shares are required for retrieval of the secret) is given in Figure 3.1. The polynomial is a line and the secret is the point where the line intersects with the y-axis. Namely, this point is the point (0,f(0)) = (0, a0). Each share is a point on the line. Any two points determine the line and hence the secret. With just a single point, the line can be any line that passes the point, and hence the secret can be any point on the y-axis.
Blakley's secret sharing scheme [Bla79] is geometric in nature. The secret is a point in an m-dimensional space. n shares are constructed with each share defining an affine hyperplane in this space; an affine hyperplane is the set of solutions x = (x1, ¼,xm) to an equation of the form a1 x1 + ¼+ am xm = b. By finding the intersection of any m of these planes, the secret (that is, the point of intersection) can be obtained. This scheme is not perfect, as the person with a share of the secret knows the secret is a point on his or her hyperplane. Nevertheless, this scheme can be modified to achieve perfect security [Sim92].
Figure 3.2: Blakley's scheme (click for a larger image)
A special case of Blakley's scheme is shown in Figure 3.2. This is based on a scenario where two shares are required to recover the secret, which means that a two-dimensional plane is used. The secret is a point in the plane. Each share is a line that passes through the point. If any two of the shares are put together, the point of intersection, which is the secret, can be easily derived.
Naor and Shamir [NS94] developed what they called visual secret sharing schemes, which are an interesting visual variant of the ordinary secret sharing schemes.
Roughly speaking, the problem can be formulated as follows: There is a secret picture to be shared among n participants. The picture is divided into n transparencies (shares) such that if any m transparencies are placed together, the picture becomes visible, but if fewer than m transparencies are placed together, nothing can be seen. Such a scheme is constructed by viewing the secret picture as a set of black and white pixels and handling each pixel separately (see [NS94] for more details). The schemes are perfectly secure and easily implemented without any cryptographic computation. A further improvement allows each transparency (share) to be an innocent picture (for example, a picture of a landscape or a picture of a building), thus concealing the fact that secret sharing is taking place.
