Secret Sharing with k-Dimensional Access Structure

Secret Sharing with k-Dimensional Access Structure

Guojun Wang (Central South University, China), Yirong Wu (Central South University, China), Geyong Min (University of Bradford, UK) and Ronghua Shi (Central South University, China)
Copyright: © 2009 |Pages: 10
DOI: 10.4018/978-1-60566-262-6.ch011
OnDemand PDF Download:
$37.50

Abstract

Secret sharing aims at distributing and sharing a secret among a group of participants efficiently. In this chapter, we propose a plane-based access structure for secret sharing. Specifically, if any two among a set of three participants in a graph contain an edge, these participants constitute a prohibited structure which is not able to recover the master key. Otherwise, the set of three participants constitute an access structure which can recover the master key. Subsequently, we extend the plane-based scheme and propose a generic k-dimensional secret sharing scheme. Finally, we analyze the performance of the proposed scheme and reveal its advantages compared to existing schemes.
Chapter Preview
Top

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.

Top

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)=a0+a1x+a2x2+...+ak-1xk-1, where a0=K.

Let x1, x2, ..., xn be n distinct numbers which are publicly known to every participant. Then the dealer evaluates: y1=f(x1), y2=f(x2), ..., yn=f(xn), 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 (xi, yi), 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.

Key Terms in this Chapter

Secret Sharing: Secret sharing aims at efficiently distributing and sharing a secret among a number of participants, and the secret can be recovered on condition that pre-specified and authorization subsets of participants can pool their shares, otherwise, the secret cannot be recovered.

Master Key: Master key is the secret shared by all participants in the system.

Linearly Independent: If a determinant consists of n vectors, and its value is non-zero, then the n vectors are linearly independent.

Participant: A member in secret sharing scheme in the system.

Prohibited Structure: The subset of participants that cannot recover the master key.

Access Structure: The subset of participants that can recover the master key.

(k, n) Threshold Secret Sharing Scheme: 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 recover the secret, but only k-1 or fewer shares cannot, where 1<=k<=n.

Threshold Value: In (k, n) threshold secret sharing scheme, k is the threshold value.

Complete Chapter List

Search this Book:
Reset