Secret sharing in graph-based prohibited structures

Hung Min Sun*, Shiuhpyng Shieh

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review

21 Scopus citations


A secret sharing scheme for the prohibited structure is a method of sharing a master key among a finite set of participants in such a way that only certain pre-specified subsets of participants cannot recover the master key. A secret sharing scheme is called perfect if any subset of participants who cannot recover the master key obtains no information regarding the master key. In this paper, we propose an efficient construction of perfect secret sharing schemes for graph-based prohibited structures where a vertex denotes a participant and an edge does a pair of participants who cannot recover the master key. The information rate of our scheme is 2/n, where n is the number of participants.

Original languageEnglish
Pages (from-to)718-724
Number of pages7
JournalProceedings - IEEE INFOCOM
StatePublished - 1 Dec 1997
EventProceedings of the 1997 16th IEEE Annual Conference on Computer Communications, INFOCOM. Part 1 (of 3) - Kobe, Jpn
Duration: 7 Apr 199712 Apr 1997

Cite this