Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Secret-sharing schemes for very dense graphs
Beimel A., Farràs O., Mintz Y. Journal of Cryptology29 (2):336-362,2016.Type:Article
Date Reviewed: Sep 14 2016

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)
Bookmark and Share
Data Encryption (E.3 )
Would you recommend this review?
Other reviews under "Data Encryption": Date
ESA/390 integrated cryptographic facility
Yeh P., Ronald M. S. IBM Systems Journal 30(2): 192-205, 1991. Type: Article
Feb 1 1992
Design and implementation of an RSA cryptosystem using multiple DSP chips
Er M., Wong D., Sethu A., Ngeow K. Microprocessors & Microsystems 15(7): 369-378, 1991. Type: Article
Nov 1 1993
An introduction to cryptography
Diffie W. (ed), Hellman M., John Wiley & Sons, Inc., New York, NY, 1984. Type: Book (9780471262336)
Feb 1 1986

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy