Computing Reviews

Secret-sharing schemes for very dense graphs
Beimel A., Farràs O., Mintz Y.  Journal of Cryptology 29(2): 336-362, 2016. Type: Article
Date Reviewed: 09/14/16

Secret-sharing schemes are common when it comes to distributing a secret among individual participants so as to ascertain that no individual has full knowledge of the secret at any given time. The paper presents an approach for maintaining small share sizes of secrets to ascertain efficiency, through the bridging of the gap that exists between the lower and upper bounds on share sizes.

The best bounds on the share sizes are formally defined in the paper, and the significance of reducing the gap between the upper and lower bounds is emphasized. In addition, the correlation between the bounds and the length of a secret is also emphasized.

The proposal is specific to “a special family of access structures,” namely those with minimal authorized sets of size two, thus enabling representation of such structures through graphs.

Through the proposal, the authors have also attempted to identify hard graphs, that is, dense graphs, and subsequently compute the best share size. The study focused on very dense graphs as otherwise a typical graph with ℓ edges “can be realized by a trivial secret-sharing scheme” with a total share size equivalent to 2ℓ times the length of the secret.

The authors aim to address two particular problems. The first is one where a graph has its edges removed iteratively with the corresponding increase in the share size studied. Second, the authors “study the removal of minimal authorized subsets from k-out-of-n threshold access structures and present a construction” of shares wherein the size of every individual secret is fairly small, that is, k << n.

This well-written paper is easy to follow for cryptography enthusiasts and researchers alike. A background in discrete mathematics would be beneficial in gaining thorough insight into the field of secret sharing.

Reviewer:  Zubair Baig Review #: CR144765 (1612-0896)

Reproduction in whole or in part without permission is prohibited.   Copyright 2017™
Terms of Use
| Privacy Policy