A construction of perfect secret-sharing schemes for the access structures based on an infinite class of graphs with low information ratio

Bo-Rong Lin (), Hui-Chuan Lu () and Hsin-Han Tung ()
Additional contact information
Bo-Rong Lin: National Chiao Tung University
Hui-Chuan Lu: National United University
Hsin-Han Tung: National United University

No 5808226, Proceedings of International Academic Conferences from International Institute of Social and Economic Sciences

Abstract: Secret-sharing is an interesting branch of modern cryptography. It is crucial in the security of information storage and has found numerous applications in many fields. In a secret-sharing scheme, there is a dealer who has a secret key, a finite set P of participants and a collection ? of subsets of P called the access structure. Each subset in ? is a qualified subset. A secret-sharing scheme is a method by which the dealer distributes a secret key among the participants in P such that only the participants in a qualified subset can recover the secret from the shares they received. If, in addition, the shares given to the participants in any unqualified subset reveal no information about the secret, then this secret-sharing scheme is called perfect. The information ratio of a perfect secret-sharing scheme is a measurement of the efficiency of the scheme. It is defined as the ratio of the maximum length (in bits) of the share given to a participant to the length of the secret. Since this ratio represents the maximum bits a participant has to remember for each bit of the secret, it is expected to be as low as possible. Constructing secret-sharing schemes with the lowest ratio becomes an important task to achieve. Given an access structure ?, the infimum of the information ratio of all possible perfect secret-sharing schemes realizing this access structure is referred to as the optimal information ratio of ?. In this paper, we consider graph-based access structures. Given a simple graph G, let each vertex of G represents a participant and each edge of G represents a minimal qualified subset. The optimal information ratio of G is the infimum of the information ratio over all possible perfect secret-sharing schemes on G. Determining the exact value of the optimal information ratio is challenging. Most results give bounds on it. In this paper, we introduce an infinite class of graphs G(n,k) whose optimal information ratio has been shown to be at least 2-2^(-n+1). Subsequently, we propose our construction of a perfect secret-sharing scheme on each G(n,k) whose information ratio is 2. Therefore, the optimal information ratio of G(n,k) lies between 2 and 2-2^(-n+1). This bound is very good when n is sufficiently large, which also means the perfect secret-sharing schemes we construct are in fact quite efficient

Keywords: perfect secret-sharing scheme; information ratio; graph-based access structure; vector space (search for similar items in EconPapers)
Pages: 1 page
Date: 2017-10
References: Add references at CitEc
Citations:

Published in Proceedings of the Proceedings of the 33rd International Academic Conference, Vienna, Oct 2017, pages 209-209

Downloads: (external link)
https://iises.net/proceedings/33rd-international-a ... =58&iid=043&rid=8226 First version, 2017

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:sek:iacpro:5808226

Access Statistics for this paper

More papers in Proceedings of International Academic Conferences from International Institute of Social and Economic Sciences
Bibliographic data for series maintained by Klara Cermakova ().