Optimal complexity of secret sharing schemes with four minimal qualified subsets

Autor:	Carles Padró, Jaume Martí-Farré, Leonor Vázquez
Rok vydání:	2010
Předmět:	Shamir's Secret Sharing Discrete mathematics Homomorphic secret sharing Linear programming Applied Mathematics Open problem Secure multi-party computation Polymatroid Verifiable secret sharing Secret sharing Computer Science Applications Mathematics
Zdroj:	Designs, Codes and Cryptography. 61:167-186
ISSN:	1573-7586 0925-1022
Popis:	The complexity of a secret sharing scheme is defined as the ratio between the maximum length of the shares and the length of the secret. This paper deals with the open problem of optimizing this parameter for secret sharing schemes with general access structures. Specifically, our objective is to determine the optimal complexity of the access structures with exactly four minimal qualified subsets. Lower bounds on the optimal complexity are obtained by using the known polymatroid technique in combination with linear programming. Upper bounds are derived from decomposition constructions of linear secret sharing schemes. In this way, the exact value of the optimal complexity is determined for several access structures in that family. For the other ones, we present the best known lower and upper bounds.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::8346dce252c90a72c79c5e76f7ca216c https://doi.org/10.1007/s10623-010-9446-0 Zobrazit plný text záznamu Full text from SpringerLink