On the optimization of bipartite secret sharing schemes

Autor: Jessica Ruth Metcalf-Burton, Carles Padró, Oriol Farràs, Leonor Vázquez
Přispěvatelé: Universitat Politècnica de Catalunya. Departament de Matemàtiques, Universitat Politècnica de Catalunya. MAK - Matemàtica Aplicada a la Criptografia, Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada IV
Rok vydání: 2011
Předmět:
Homomorphic secret sharing
Matemàtiques i estadística::Investigació operativa::Programació matemàtica [Àrees temàtiques de la UPC]
Codificació
Teoria de la
Secret sharing
Upper and lower bounds
Matemàtiques i estadística::Anàlisi numèrica [Àrees temàtiques de la UPC]
Combinatorics
Linear programming
Matemàtiques i estadística::Probabilitat [Àrees temàtiques de la UPC]
Programació (Matemàtica)
65 Numerical analysis::65K Mathematical programming
optimization and variational techniques [Classificació AMS]
Matroides
Access structure
Mathematics
Anàlisi numèrica
Programming (Mathematics)
Multipartite secret sharing
94 Information And Communication
Circuits::94A Communication
information [Classificació AMS]
Applied Mathematics
Criptografia
90C Mathematical programming
Polymatroids
Programació lineal
Computer Science Applications
Matroids
Shamir's Secret Sharing
Cryptography
Bipartite graph
Secure multi-party computation
Verifiable secret sharing
Coding theory
Matemàtiques i estadística::Investigació operativa::Optimització [Àrees temàtiques de la UPC]
Numerical analysis
Zdroj: UPCommons. Portal del coneixement obert de la UPC
Universitat Politècnica de Catalunya (UPC)
Recercat. Dipósit de la Recerca de Catalunya
instname
ISSN: 1573-7586
0925-1022
DOI: 10.1007/s10623-011-9552-7
Popis: Optimizing the ratio between the maximum length of the shares and the length of the secret value in secret sharing schemes for general access structures is an extremely difficult and long-standing open problem. In this paper, we study it for bipartite access structures, in which the set of participants is divided in two parts, and all participants in each part play an equivalent role. We focus on the search of lower bounds by using a special class of polymatroids that is introduced here, the tripartite ones. We present a method based on linear programming to compute, for every given bipartite access structure, the best lower bound that can be obtained by this combinatorial method. In addition, we obtain some general lower bounds that improve the previously known ones, and we construct optimal secret sharing schemes for a family of bipartite access structures.
Databáze: OpenAIRE
Externí odkaz: