Paper 2017/919
Improving the Linear Programming Technique in the Search for Lower Bounds in Secret Sharing
Oriol Farras and Tarik Kaced and Sebastia Martin and Carles Padro
Abstract
We present a new improvement in the Linear Programming technique to derive bounds on information theoretic problems. In our case, we deal with the search for lower bounds on the information ratio of secret sharing schemes. We obtain non-Shannon-type bounds without using information inequalities explicitly. Our new techniques makes it possible to determine the optimal information ratio of linear secret sharing schemes for all access structures on $5$ participants. New lower bounds are presented also for graph-based access structures on six participants and for some small matroidal access structures. In particular, we determine the optimal information ratio of the linear secret sharing schemes for the ports of the Vamos matroid.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Preprint. MINOR revision.
- Keywords
- Secret sharingInformation inequalitiesRank inequalitiesCommon informationLinear Programming
- Contact author(s)
- carles padro @ upc edu
- History
- 2022-03-30: last of 3 revisions
- 2017-09-24: received
- See all versions
- Short URL
- https://ia.cr/2017/919
- License
-
CC BY