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:


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


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)=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

Search this Book:
Editorial Advisory Board
Table of Contents
Borko Furht
Shiguo Lian, Yan Zhang
Shiguo Lian, Yan Zhang
Chapter 1
Pramod A. Jamkhedkar, Gregory L. Heileman
Rights expression languages (RELs) form a central component of digital rights management (DRM) systems. The process of development of RELs... Sample PDF
Rights Expression Languages
Chapter 2
Deepali Brahmbhatt, Mark Stamp
This chapter presents a digital rights management (DRM) system designed for streaming media. A brief, general introduction to DRM is also provided... Sample PDF
Digital Rights Management for Streaming Media
Chapter 3
Jean-Henry Morin
This chapter introduces and discusses much needed alternatives to the traditional either/or debate on total security of secure multimedia... Sample PDF
Rethinking DRM Using Exception Management
Chapter 4
Mercè Serra Joan, Bert Greevenbosch, Anja Becker, Harald Fuchs
This chapter gives an overview of the Open Mobile AllianceTM Digital Rights Management (OMA DRM) standard, which allows for the secure distribution... Sample PDF
Overview of OMA Digital Rights Management
Chapter 5
Hugo Jonker, Sjouke Mauw
The use of Digital Rights Management (DRM) systems involves several stakeholders, such as the content provider, the license provider, and the user... Sample PDF
Discovering the Core Security Requirements of DRM Systems by Means of Objective Trees
Chapter 6
Pallavi Priyadarshini, Mark Stamp
Peer-to-peer (P2P) networks have proliferated and become ubiquitous. A school of thought has emerged that harnessing the established user-base and... Sample PDF
Digital Rights Management for Untrusted Peer-to-Peer Networks
Chapter 7
L. Badia, A. Erta, U. Malesci
Traditional analog video surveillance systems technology has recently become inadequate to face the massive demand of security systems consisting of... Sample PDF
Pervasive Video Surveillance Systems Over TCP/IP Networks
Chapter 8
Ramya Venkataramu, Mark Stamp
Digital Rights Management (DRM) technology is used to control access to copyrighted digital content. Apple employs a DRM system known as Fairplay in... Sample PDF
P2PTunes: A Peer-to-Peer Digital Rights Management System
Chapter 9
Nicolas Anciaux, Luc Bouganim, Philippe Pucheral
This chapter advocates the convergence between Access Control (AC) models, focusing on the granularity of sharing, and Digital Right Management... Sample PDF
A Hardware Approach for Trusted Access and Usage Control
Chapter 10
Ionut Florescu
Regarding fundamental protocols in cryptography, the Diffie-Hellman (Diffie and Hellman, 1976) public key exchange protocol is one of the oldest and... Sample PDF
A Summary of Recent and Old Results on the Security of the Diffie-Hellman Key Exchange Protocol in Finite Groups
Chapter 11
Guojun Wang, Yirong Wu, Geyong Min, Ronghua Shi
Secret sharing aims at distributing and sharing a secret among a group of participants efficiently. In this chapter, we propose a plane-based access... Sample PDF
Secret Sharing with k-Dimensional Access Structure
Chapter 12
Supavadee Aramvith, Rhandley D. Cajote
Presently, both wireless communications and multimedia communications have experienced unequaled rapid growth and commercial success. Building on... Sample PDF
Wireless Video Transmission
Chapter 13
M. Hassan Shirali-Shahreza, Mohammad Shirali-Shahreza
Establishing hidden communication is an important subject of discussion that has gained increasing importance recently, particularly with the... Sample PDF
A Survey of Information Hiding
Chapter 14
Fan Zhang
The digital multimedia, including text, image, graphics, audio, video, and so forth, has become a main way for information communication along with... Sample PDF
Digital Watermarking Capacity and Detection Error Rate
Chapter 15
Digital Watermarking  (pages 277-297)
Aidan Mooney
As Internet usage continues to grow, people are becoming more aware of the need to protect the display and presentation of digital documents.... Sample PDF
Digital Watermarking
Chapter 16
Pradeep K. Atrey, Abdulmotaleb El Saddik, Mohan Kankanhalli
Digital video authentication has been a topic of immense interest to researchers in the past few years. Authentication of a digital video refers to... Sample PDF
Digital Video Authentication
Chapter 17
Tieyan Li
The multimedia community is moving from monolithic applications to more flexible and scalable proliferate solutions. Security issues such as access... Sample PDF
Flexible Multimedia Stream Authentication
Chapter 18
K-G Stenborg
Media that is distributed digitally can be copied and redistributed illegally. Embedding an individual watermark in the media object for each... Sample PDF
Scalable Distribution of Watermarked Media
Chapter 19
Hafiz Malik
This chapter provides critical analysis of current state-of-the-art in steganography. First part of the this chapter provides the classification of... Sample PDF
Critical Analysis of Digital Steganography
Chapter 20
Esther Palomar, Juan M.E. Tapiador, Julio C. Hernandez-Castro, Arturo Ribagorda
Perhaps the most popular feature offered by Peer-to-Peer (P2P) networks is the possibility of having several replicas of the same content... Sample PDF
Secure Content Distribution in Pure P2P
Chapter 21
Andreas U. Schmidt, Nicolai Kuntze
Security in the value creation chain hinges on many single components and their interrelations. Trusted Platforms open ways to fulfil the pertinent... Sample PDF
Trust in the Value-Creation Chain of Multimedia Goods
Chapter 22
Goo-Rak Kwon, Sung-Jea Ko
The objective of this chapter introduces an advanced encryption of MP3 and MPEG-4 coder with a quality degradation-based security model. For the MP3... Sample PDF
Copyright Protection of A/V Codec for Mobile Multimedia Devices
Chapter 23
Frank Y. Shih, Yi-Ta Wu
Steganography is the art of hiding secret data inside other innocent media file. Steganalysis is the process of detecting hidden data which are... Sample PDF
Digital Steganography Based on Genetic Algorithm
Chapter 24
Guangjie Liu, Shiguo Lian, Yuewei Dai, Zhiquan Wang
Image steganography is a common form of information hiding which embeds as many message bits into images and keep the introduced distortion... Sample PDF
Adaptive Image Steganography Based on Structural Similarity Metric
Chapter 25
Shiguo Lian
Video watermarking technique embeds some information into videos by modifying video content slightly. The embedded information, named watermark, may... Sample PDF
A Survey on Video Watermarking
Chapter 26
Minglei Liu, Ce Zhu
Digital watermarking is a useful and powerful tool for multimedia security such as copyright protection, tamper proofing and assessment, broadcast... Sample PDF
Multiple Description Coding with Application in Multimedia Watermarking
Chapter 27
Hsuan T. Chang, Chih-Chung Hsu
This chapter introduces a pioneer concept in which multiple images are simultaneously considered in the compression and secured distribution... Sample PDF
Fractal-Based Secured Multiple-Image Compression and Distribution
About the Contributors