Several Types Of Hypergraph Access Structures And Their Optimal Information Rates

Secret sharing is crytology technique for avoiding that secret is the too concentrated. Since the concept of secret sharing is proposed by Shamir and Blakley in 1979 independently, it is concerned by many scholars at home and abroad. With the in-depth research, secret sharing is widely used in practice, such as, communication key management, bank vault, missile control launch. Secret sharing scheme is a protocol that the key can be shared among a set of participants, requiring only qualified subset can recover the key. If unqualified subset can not get any information about the key, the scheme is perfect. The set of all qualified subsets is called the access structure, which can be realized by multiple perfect secret sharing schemes. So in terms of efficiency, we need calculated the highest information rate in the multiple secret sharing schemes, which is called the optimal information rate. Given an access structure, calculateing its optimal information rate is often very difficult. Giovanni Di Crescenzo et al. calculate the optimal information rate of hypercycle access structure with n(n≥5) hyperedges is equal to 2/3. We study the hypergraphs with three hyperedges and hypercycle access structure with four hyperedges and their optimal information rates.The research results of this paper are showed as follow:1. On the basis of hypergraph access structure with three hyperedges, first of all, we show a sufficient and necessary condition of connected hypergraph, and get a conclusion which hyperstar with three hyperedges is hypercycle by the definition of hypercycle. According to the above conclusions, we prove that the any connected hypergraph with three hyperedges is only hyperpath or hypercycle, in particular, the all 144 kinds of hypergraph access structure with three hyperedges are given. Then, there exist the ideal hypercycle access structures with three hyperedges by examples which are realized by constructing an ideal secret sharing scheme. We prove that the optimal information rete of hyperpath and non-ideal hypercycle access structures with three hyperedges are equal to 2/3 by applying information theory and λ-decomposition. The above mentiond conclusions are applicable to any number of participants. So, we give the all hypergraph access structures with three hyperedges in which all of each other are not isomorphic on six ang seven participants, and calculate their optimal information rates.2. There are 6 kinds of hypercycle access structures with four hyperedges in the sense of hypergraph isomorphism, and classify them according to the access structures ideal or not, one kind is that any hyperedge has not their own independent point, another kind is that there are at least one hyperedge has their own independent point, and the exact value of the optimal information rate is given for every access structure. The above mentiond conclusions are applicable to any number of participants. When the number of participant is determined, the hypercycle access structure with four hyperedges in which all of each other are not isomorphic and their optimal information rate are given conveniently and accurately.