Hypergraph decomposition and secret sharing

被引:20
作者
Di Crescenzo, Giovanni [2 ]
Galdi, Clemente [1 ]
机构
[1] Univ Naples Federico 2, Dipartimento Sci Fis, I-80126 Naples, Italy
[2] Telcordia Technol Inc, Piscataway, NJ 08854 USA
关键词
Cryptography; Secret sharing; Hypergraph decomposition; ACCESS STRUCTURES; INFORMATION RATE; SCHEMES;
D O I
10.1016/j.dam.2008.04.001
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
A secret sharing scheme is a protocol by which a dealer distributes a secret among a set of participants in such a way that only qualified sets of them can reconstruct the value of the secret whereas any non-qualified subset of participants obtain no information at all about the value of the secret. Secret sharing schemes have always played a very important role for cryptographic applications and in the construction of higher level cryptographic primitives and protocols. In this paper we investigate the construction of efficient secret sharing schemes by using a technique called hypergraph decomposition, extending in a non-trivial way the previously studied graph decomposition techniques. A major advantage of hypergraph decomposition is that it applies to any access structure, rather than only structures representable as graphs. As a consequence, the application of this technique allows us to obtain secret sharing schemes for several classes of access structures (such as hyperpaths, hypercycles, hyperstars and acyclic hypergraphs) with improved efficiency over previous results. Specifically, for these access structures, we present secret sharing schemes that achieve optimal information rate. Moreover, with respect to the average information rate, our schemes improve on previously known ones. In the course of the formulation of the hypergraph decomposition technique, we also obtain an elementary characterization of the ideal access structures among the hyperstars, which is of independent interest. (C) 2008 Elsevier B.V. All rights reserved.
引用
收藏
页码:928 / 946
页数:19
相关论文
共 27 条
[1]  
[Anonymous], 1990, Introduction to Algorithms
[2]  
[Anonymous], 1991, ELEMENTS INFORM THEO
[3]  
BENALOH J, 1990, LECT NOTES COMPUT SC, V403, P27
[4]  
Blakley G. R., 1979, 1979 International Workshop on Managing Requirements Knowledge (MARK), P313, DOI 10.1109/MARK.1979.8817296
[5]   Tight Bounds on the Information Rate of Secret Sharing Schemes [J].
Carlo Blundo ;
Alfredo De Santis ;
Roberto De Simone ;
Ugo Vaccaro .
Designs, Codes and Cryptography, 1997, 11 (2) :107-110
[6]   GRAPH DECOMPOSITIONS AND SECRET SHARING SCHEMES [J].
BLUNDO, C ;
DESANTIS, A ;
STINSON, DR ;
VACCARO, U .
JOURNAL OF CRYPTOLOGY, 1995, 8 (01) :39-64
[7]   On the information rate of secret sharing schemes [J].
Blundo, C ;
DeSantis, A ;
Gargano, L ;
Vaccaro, U .
THEORETICAL COMPUTER SCIENCE, 1996, 154 (02) :283-306
[8]  
Brickell E. F., 1991, Journal of Cryptology, V4, P123, DOI 10.1007/BF00196772
[9]  
Capocelli R. M., 1993, Journal of Cryptology, V6, P157, DOI 10.1007/BF00198463
[10]   The size of a share must be large [J].
Csirmaz, L .
JOURNAL OF CRYPTOLOGY, 1997, 10 (04) :223-231