Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/59108
Title: Secret sharing schemes and polymatroids
Authors: Yang, An
Keywords: DRNTU::Science::Mathematics::Discrete mathematics::Cryptography
Issue Date: 2014
Source: Yang, A. (2014). Secret sharing schemes and polymatroids. Doctoral thesis, Nanyang Technological University, Singapore.
Abstract: Secret sharing, which refers to methods of distributing a secret value among a group of participants, is a very important primitive in cryptology. This thesis contains some contribution to this topic. The results that are presented herein deal with 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 both open problems, polymatroids are a powerful tool. On one hand, ideal multipartite secret sharing schemes are strongly connected to polymatroids. On the other hand, the entropies of shares of a scheme determine a polymatroid, and because of that, they are fundamental in the search of lower bounds of the length of the shares. For the first open problem, some new and useful families of ideal multipartite access structures are found by using integer polymatroids. As a result the proofs for the existence of ideal secret sharing schemes for them are simplified in great measure. Regarding the second open problem, we present positive and negative results about the only known technique to find lower bounds: linear programming. The positive result are obtained by strengthening this method. The negative ones show the limitation of this method trying to improve the asymptotic lower bounds.
URI: http://hdl.handle.net/10356/59108
metadata.item.grantfulltext: restricted
metadata.item.fulltext: With Fulltext
Appears in Collections:SPMS Theses

Files in This Item:
File Description SizeFormat 
thesis.pdf691.57 kBAdobe PDFThumbnail
View/Open

Page view(s)

283
checked on Jan 11, 2020

Download(s)

165
checked on Jan 11, 2020

Google ScholarTM

Check

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.