On secret sharing schemes, matroids and polymatroids
| Autor: | Carles Padró, Jaume Martí-Farré |
|---|---|
| Přispěvatelé: | Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada IV, Universitat Politècnica de Catalunya. MAK - Matemàtica Aplicada a la Criptografia |
| Jazyk: | angličtina |
| Rok vydání: | 2010 |
| Předmět: |
TheoryofComputation_MISCELLANEOUS
polymatroids Homomorphic secret sharing Combinatorial analysis 05 Combinatorics::05B Designs and configurations [Classificació AMS] Matemàtiques i estadística::Matemàtica discreta::Combinatòria [Àrees temàtiques de la UPC] Secret sharing Matroid Combinatorics QA1-939 Matroides Mathematics Access structure Discrete mathematics Applied Mathematics 94 Information And Communication Circuits::94A Communication information [Classificació AMS] Criptografia optimization of secret sharing schemes for general access structures Computer Science Applications Shamir's Secret Sharing Matroids Computational Mathematics ideal secret sharing schemes secret sharing Secure multi-party computation Cryptography Polymatroid Verifiable secret sharing Informàtica::Seguretat informàtica::Criptografia [Àrees temàtiques de la UPC] matroids Anàlisi combinatòria |
| Zdroj: | UPCommons. Portal del coneixement obert de la UPC Universitat Politècnica de Catalunya (UPC) Recercat. Dipósit de la Recerca de Catalunya instname Journal of Mathematical Cryptology, Vol 4, Iss 2, Pp 95-120 (2010) |
| 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. The optimization of this parameter for general access structures is an important and very difficult open problem in secret sharing. We explore in this paper the connections of this open problem with matroids and polymatroids. Matroid ports were introduced by Lehman in 1964. A forbidden minor characterization of matroid ports was given by Seymour in 1976. These results precede the invention of secret sharing by Shamir in 1979. Important connections between ideal secret sharing schemes and matroids were discovered by Brickell and Davenport in 1991. Their results can be restated as follows: every ideal secret sharing scheme defines a matroid, and its access structure is a port of that matroid. Our main result is a lower bound on the optimal complexity of access structures that are not matroid ports. Namely, by using the aforementioned characterization of matroid ports by Seymour, we generalize the result by Brickell and Davenport by proving that, if the length of every share in a secret sharing scheme is less than 3/2 times the length of the secret, then its access structure is a matroid port. This generalizes and explains a phenomenon that was observed in several families of access structures. In addition, we introduce a new parameter to represent the best lower bound on the optimal complexity that can be obtained by taking into account that the joint Shannon entropies of a set of random variables define a polymatroid. We prove that every bound that is obtained by this technique for an access structure applies to its dual as well. Finally, we present a construction of linear secret sharing schemes for the ports of the Vamos and the non-Desargues matroids. In this way new upper bounds on their optimal complexity are obtained, which are a contribution on the search of access structures whose optimal complexity lies between 1 and 3/2. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|