Cryptology ePrint Archive: Report 2017/1232

Optimal Linear Secret Sharing Schemes for Graph Access Structures on Six Participants

Motahhareh Gharahi and Shahram Khazaei

Abstract: We review the problem of finding the optimal information ratios of graph access structures on six participants. Study of such access structures were initiated by van Dijk [Des. Codes Cryptogr. 15 (1998), 301-321].Through a sequence of follow up works, exact values of optimal information ratios of nine access structures, out of 18 initially unsolved non-isomorphic ones, were determined. Very recently [O. Farras et al. Cryptology ePrint Archive: Report 2017/919], for each of the remained such cases, the known lower bound on the optimal information ratio of linear secret sharing schemes was improved, establishing the optimal information ratio of linear secret sharing schemes for two of them. Here, for each of the other seven cases, we provide a new upper bound on the optimal information ratio of linear secret sharing schemes; our improved upper bounds match the corresponding recently presented lower bounds. Improved upper bounds are achieved using decomposition techniques. As an additional contribution, we present a new decomposition technique, called $(\lambda,\omega)$-weighted decomposition, which is a generalization of all known decomposition techniques.

Category / Keywords: cryptographic protocols / Secret sharing, Optimal information ratio, Decomposition techniques

Date: received 21 Dec 2017

Contact author: gharahi motahhareh at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20171222:202348 (All versions of this report)

Short URL: ia.cr/2017/1232

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]