Secret Sharing with k-Dimensional Access Structure

Introduction

Secret sharing is an important method of information security and data secrecy, which is a vital branch of cryptology. Moreover, it plays a key role in secure storage and secure transmission of important information. Secret sharing aims at distributing and sharing a secret among a number of participants efficiently and the secret can be recovered on condition that the pre-specified and authorized subsets of participants can pool their shares, otherwise, the secret cannot be recovered. Secret sharing mechanism is especially suitable for applications with many partners involved.

(Shamir, 1979; Blackley, 1979) respectively proposed the original mechanisms of secret sharing, both of which are (k, n) threshold schemes. The scheme in (Shamir, 1979) is based on Lagrange interpolation polynomial while the scheme in (Blackley, 1979) is based on projection geometry theory. In a (k, n) threshold secret sharing scheme, as shown in Figure 1, the trusted dealer delivers the distinct secret shares to n participants. At least k or more participants can pool their secret shares in order to reconstruct the secret, but only k-1 or fewer shares cannot.

Figure 1.

(k, n) threshold secret sharing mechanism

The rest of this chapter is organized as follows: Section 2 introduces the research background of secret sharing, including (k, n) threshold secret sharing and general access structure secret sharing. Section 3 introduces three graph-based secret sharing schemes. A plane-based general access structure for secret sharing is proposed in Section 4. In Section 5, we propose a generic k-dimensional secret sharing scheme. Finally, Section 6 presents the conclusion and future work.

Background: Secret Sharing Schemes

In this section, we firstly introduce (k, n) threshold secret sharing schemes and then describe the secret sharing schemes based on general access structure.

(k, n) Threshold Secret Sharing Schemes

Many methods are available to implement (k, n) threshold secret sharing, such as Lagrange polynomial interpolation (Shamir, 1979), projection geometry theory (Blackley, 1979), Vector Space (Stmson, 1995; Xu, 2002), and Chinese Remainder Theorem (Pei, 2002). The commonly used scheme in (Shamir, 1979), which is based on Lagrange interpolation polynomial, is introduced as follows:

Given the master key K, the dealer selects at random a k-1 degree polynomial f(x)=a₀+a₁x+a₂x²+...+a_k-1x^k-1, where a₀=K.

Let x₁, x₂, ..., x_n be n distinct numbers which are publicly known to every participant. Then the dealer evaluates: y₁=f(x₁), y₂=f(x₂), ..., y_n=f(x_n), and delivers them to each participant over a secure channel.

At least k participants are required to use the Lagrange interpolation polynomial to recover the secret. With the knowledge of the set of k points (x_i, y_i), the k-1 degree polynomial f(x) can be uniquely determined below

So,

Obviously, if only k-1 or fewer shares are shown, there is no information about K available and thus it cannot be recovered.