Multipartite secret sharing schemes

• Autores: Oriol Farràs Ventura
• Directores de la Tesis: Carles Padró Laimón (dir. tes.)
• Lectura: En la Universitat Politècnica de Catalunya (UPC) ( España ) en 2010
• Idioma: inglés
• Tribunal Calificador de la Tesis: Marc Noy Serrano (presid.) , Paz Morillo Bosch (secret.) , Ronald Cramer (voc.)
• Enlaces
  • Tesis en acceso abierto en: docs.google.com
• Resumen

  • This thesis is dedicated to the study of secret sharing schemes, which are cryptographic methods to share information in a secure way. The topics that are considered in the thesis are two of the main open problems in secret sharing: the characterization of the ideal access structures and the optimization of the length of the shares for general access structures. These open problems are studied for multipartite secret sharing schemes. In these schemes the set of participants is divided into parts and the participants in each part have the same rights to obtain the secret.

    The results of the thesis are based on a new combinatorial property of secret sharing schemes, which is a connection between ideal multipartite secret sharing schemes and integer polymatroids. It provides new sufficient conditions and necessary conditions for an access structure to be ideal. Moreover, this connection is also used in the construction ideal linear multipartite secret sharing schemes. These results are useful for the study of multipartite access structures in which the number of parts is small in relation to the number of participants, and multipartite access structures in which the parts are related in a special way. This is the case of the family of hierarchical access structures, which are the ones in which the participants can be hierarchically ordered, and the family of tripartite access structures. Applying these results, the ideal access structures in these families are completely characterized. All the ideal multipartite secret sharing schemes presented in the literature are related to a particular family of integer polymatroids, the boolean ones. The analysis of these polymatroids leds to the find of new ideal multipartite secret sharing schemes.

    The optimization of the length of the shares is also studied for multipartite secret sharing schemes, in particular for the bipartite ones. The main results are a new method to find bound on the length of the shares that combines linear programming and polymatroids, and a new family of optimal bipartite linear secret sharing schemes.