Paper 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
Secret sharingOptimal information ratioDecomposition techniques
Contact author(s)
gharahi motahhareh @ gmail com
History
2017-12-22: received
Short URL
https://ia.cr/2017/1232
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1232,
      author = {Motahhareh Gharahi and Shahram Khazaei},
      title = {Optimal Linear Secret Sharing Schemes for Graph Access Structures on Six Participants},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1232},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/1232}},
      url = {https://eprint.iacr.org/2017/1232}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.