Security

Secret Sharing Schemes for Very Dense Graphs

Download Now Date Added: Jul 2012
Format: PDF

A secret-sharing scheme realizes a graph if every two vertices connected by an edge can reconstruct the secret while every independent set in the graph does not get any information on the secret. Similar to secret-sharing schemes for general access structures, there are gaps between the known lower bounds and upper bounds on the share size for graphs. Motivated by the question of what makes a graph "Hard" for secret-sharing schemes (that is, require large shares), the authors study very dense graphs, that is, graphs whose complement contains few edges.