Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

Finding Lower Bounds on the Complexity of Secret Sharing Schemes by Linear Programming

Carles Padró, Leonor Vázquez

Published Jan 1, 2010• 13 citations
Publisher
DOI
10.1007/978-3-642-12200-2_31

Related papers

Finding lower bounds on the complexity of secret sharing schemes by linear programming

Carles Padró, Leonor Vázquez, Yang An

Discrete Applied Mathematics•Nov 9, 2012•29 citations

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

Oriol Farràs, Tarik Kaced, Sebastià Martín +1 more

Lecture notes in computer science•Jan 1, 2018•20 citations

Lower bounds for robust secret sharing schemes

Carlo Blundo, Alfredo De Santis

Information Processing Letters•Sep 1, 1997•22 citations

A Lower Bound on the Share Size of Leakage-Resilient Secret-Sharing Schemes

Sabyasachi Dutta, Shaoquan Jiang, Reihaneh Safavi–Naini

Fields Institute communications•Nov 16, 2023•0 citations

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

Oriol Farràs, Tarik Kaced, Sebastià Martín Mollevi +1 more

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.

IEEE Transactions on Information Theory•Jun 29, 2020•23 citations

Symmetries in Linear Programming for Information Inequalities

Emirhan Gürpınar

Secret sharing is a central topic in information-theoretical cryptography. In a secret sharing scheme a random secret is distributed among participants so that only the qualified subsets of parties can recover the secret. In this paper we improve previously known [13] lower bounds on the size of the largest share for several specific access structures. Our approach is based on non-Shannon-type information inequalities. We employ the linear programming (LP) technique that permits to apply new information inequalities indirectly. To reduce computational complexity of the involved linear programs we extensively use symmetry considerations.

arXiv:2201.11656•IEEE International Symposium on Information Theory (ISIT)•Jun 26, 2022•2 citations
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.
Secret sharing is a central topic in information-theoretical cryptography. In a secret sharing scheme a random secret is distributed among participants so that only the qualified subsets of parties can recover the secret. In this paper we improve previously known [13] lower bounds on the size of the largest share for several specific access structures. Our approach is based on non-Shannon-type information inequalities. We employ the linear programming (LP) technique that permits to apply new information inequalities indirectly. To reduce computational complexity of the involved linear programs we extensively use symmetry considerations.