Paper 2017/919

Improving the Linear Programming Technique in the Search for Lower Bounds in Secret Sharing

Oriol Farràs, Tarik Kaced, Sebastià Martín, and Carles Padró

Abstract

We present a new improvement in the linear programming technique to derive lower bounds on the information ratio of secret sharing schemes. We obtain non-Shannon-type bounds without using information inequalities explicitly. Our new technique makes it possible to determine the optimal information ratio of linear secret sharing schemes for all access structures on 5 participants and all graph-based access structures on 6 participants. In addition, new lower bounds are presented also for some small matroid ports and, in particular, the optimal information ratios of the linear secret sharing schemes for the ports of the Vamos matroid are determined.

Note: Extended version of the paper in EUROCRYPT 20018.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in EUROCRYPT 2018
Keywords
Secret sharingInformation inequalitiesRank inequalitiesCommon informationLinear Programming
Contact author(s)
carles padro @ upc edu
oriol farras @ urv cat
History
2022-03-30: last of 3 revisions
2017-09-24: received
See all versions
Short URL
https://ia.cr/2017/919
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/919,
      author = {Oriol Farràs and Tarik Kaced and Sebastià Martín and Carles Padró},
      title = {Improving the Linear Programming Technique in the Search for Lower Bounds in Secret Sharing},
      howpublished = {Cryptology ePrint Archive, Paper 2017/919},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/919}},
      url = {https://eprint.iacr.org/2017/919}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.