dc.contributor
Universitat Politècnica de Catalunya. Departament de Matemàtiques
dc.contributor
Universitat Politècnica de Catalunya. MAK - Matemàtica Aplicada a la Criptografia
dc.contributor.author
Padró Laimon, Carles
dc.contributor.author
Vázquez González, Leonor
dc.contributor.author
Yang, An
dc.date.issued
2013-05-01
dc.identifier
Padro, C., Vázquez, L., Yang, A. Finding lower bounds on the complexity of secret sharing schemes by linear programming. "Discrete applied mathematics", 1 Maig 2013, vol. 161, núm. 7-8, p. 1072-1084.
dc.identifier
https://hdl.handle.net/2117/105967
dc.identifier
10.1016/j.dam.2012.10.020
dc.description.abstract
Optimizing the maximum, or average, length of the shares in relation to the length of the secret for every given access structure is a difficult and long-standing open problem in cryptology. Most of the known lower bounds on these parameters have been obtained by implicitly or explicitly using that every secret sharing scheme defines a polymatroid related to the access structure. The best bounds that can be obtained by this combinatorial method can be determined by using linear programming, and this can be effectively done for access structures on a small number of participants.
By applying this linear programming approach, we improve some of the known lower bounds for the access structures on five participants and the graph access structures on six participants for which these parameters were still undetermined. Nevertheless, the lower bounds that are obtained by this combinatorial method are not tight in general. For some access structures, they can be improved by adding to the linear program non-Shannon information inequalities as new constraints. We obtain in this way new separation results for some graph access structures on eight participants and for some ports of non-representable matroids. Finally, we prove that, for two access structures on five participants, the combinatorial lower bound cannot be attained by any linear secret sharing scheme
dc.description.abstract
Peer Reviewed
dc.description.abstract
Postprint (author's final draft)
dc.format
application/pdf
dc.relation
http://www.sciencedirect.com/science/article/pii/S0166218X12004003?via%3Dihub
dc.rights
http://creativecommons.org/licenses/by-nc-nd/3.0/es/
dc.rights
Attribution-NonCommercial-NoDerivs 3.0 Spain
dc.subject
Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Combinatòria
dc.subject
Àrees temàtiques de la UPC::Matemàtiques i estadística::Anàlisi numèrica::Modelització matemàtica
dc.subject
Combinatorial probabilities
dc.subject
Numerical analysis
dc.subject
Secret sharing
dc.subject
linear programming
dc.subject
non-Shannon information inequalities
dc.subject
Combinacions (Matemàtica)
dc.subject
Anàlisi numèrica
dc.subject
Classificació AMS::60 Probability theory and stochastic processes::60C05 Combinatorial probability
dc.subject
Classificació AMS::65 Numerical analysis::65K Mathematical programming, optimization and variational techniques
dc.title
Finding lower bounds on the complexity of secret sharing schemes by linear programming
