Cryptology ePrint Archive: Report 2016/928

The complexity of the connected graph access structure on seven participants

Massoud Hadian Dehkordi and Ali Safi

Abstract: In this paper, we study an important problem in secret sharing that determines the exact value or bound for the complexity. First, we used induced subgraph complexity of the graph G with access structure, Gama, to obtain a lower bound on the complexity of the graph G. Secondly, by applying decomposition techniques we obtain an upper bound on the complexity of the graph G. We determine the exact values of the complexity for each of the ten graph access structures on seven participants. Also, we improve the value bound of the complexity of the six graph access structures with seven participants.

Category / Keywords: foundations / Access structure, Complexity, Secret sharing scheme,  Connected graph,  Induced subgraph

Date: received 25 Sep 2016, last revised 27 Sep 2016

Contact author: alisafi at iust ac ir

Available format(s): PDF | BibTeX Citation

Version: 20160928:003411 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]