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
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.
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.
(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
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
Shiguo Lian, Yan Zhang
Shiguo Lian, Yan Zhang
Pramod A. Jamkhedkar, Gregory L. Heileman
Deepali Brahmbhatt, Mark Stamp
Mercè Serra Joan, Bert Greevenbosch, Anja Becker, Harald Fuchs
Hugo Jonker, Sjouke Mauw
Pallavi Priyadarshini, Mark Stamp
L. Badia, A. Erta, U. Malesci
Ramya Venkataramu, Mark Stamp
Nicolas Anciaux, Luc Bouganim, Philippe Pucheral
Guojun Wang, Yirong Wu, Geyong Min, Ronghua Shi
Supavadee Aramvith, Rhandley D. Cajote
M. Hassan Shirali-Shahreza, Mohammad Shirali-Shahreza
Pradeep K. Atrey, Abdulmotaleb El Saddik, Mohan Kankanhalli
Esther Palomar, Juan M.E. Tapiador, Julio C. Hernandez-Castro, Arturo Ribagorda
Andreas U. Schmidt, Nicolai Kuntze
Goo-Rak Kwon, Sung-Jea Ko
Frank Y. Shih, Yi-Ta Wu
Guangjie Liu, Shiguo Lian, Yuewei Dai, Zhiquan Wang
Minglei Liu, Ce Zhu
Hsuan T. Chang, Chih-Chung Hsu