TWO-LEVEL SECRET SHARING SCHEMES BASED ON CRITICAL SETS OF REVERSE EDGE-MAGIC LABELINGS
Abstract
In this paper, we propose two-level secret sharing scheme based critical sets on a reverse edge magic labeling of star graphs. It is a scheme which creates two types of hierarchical sets. The first set contains share that are more powerful than the share in the second set. We name this scheme the departmental secret sharing scheme. These two secret sharing schemes are constructed by critical sets of reverse edge-magic labelling.
We build banking secret sharing scheme that will share a secret among one bank manager and several sets of authorized staff members.
INTRODUCTION
Blakley [3], Chaum [5] and Shamir [7] were first introduced dependently the notion of secret sharing scheme in 1979.A secret sharing scheme is a method of allocating a secret S among a finite set of customers C ={c1, c2, · , cn} in such a way that if the customers in A ?C are capable to know the secret, then their partial information by pooling together, they can reconstruct the secret S; but any B ? C, which is not qualified to know S, cannot reconstruct the secret.
The key S which is chosen by a special customer d, called a dealer, and it usually assumed that d ? C. The share means that dealer gives partial information to each customer which is a tool to reveal the secret S. An access structure ? is the family of all the subsets of customers that are able to reconstruct the secret. The sets belonging to the access structure ? are called authorized sets and those not belonging to the access structure are termed as unauthorized sets.
A two-level secret sharing scheme is a scheme which produces two kinds of hierarchical sets. The first set (the highest rank) contains shares that are more powerful (important) than the shares in the second set.
In our previous paper , we construct a secret sharing scheme based on critical sets of reverse edge magic graph labelling by using Karmin- Greene- Helman(KGH) Algorithm[ 6 ]. In this paper, we continue our work to plan a two-level secret sharing scheme based on critical sets of reverse edge magic graph labeling. We provide two different types of such schemes, with two different possible applications.
The first scheme distributes shares of a secret among two sets. The first set (the highest rank set) contains a single person s0, called a supervisor, and the second set contains a number of chosen people. In the first scheme ,the access structure ? is the family of all sets of the form {s0,p} where p belongs to the second set. We call the first scheme the supervisional secret sharing scheme.
In the proposed second scheme, the first set (the highest rank set) contains a single person s0. The second set S2 contains k departments, namely S2 = {D1, D2, ·, Dk} where each department Di consists of di authorised people. In the second scheme ,the access structure ? in this second scheme is the family of all sets of the form {s0, x1, x2, · , xk } where xi ? Di. We name this scheme the departmental secret sharing scheme. These two secret sharing schemes are constructed by critical sets of reverse edge-magic labeling. The definitions of reverse edge-magic labelling, critical sets and its related results will be existing in Section II. The proposed schemes will be enlightened in Section III and a conclusion is located in Section IV.
BASIC THEORY
In this paper, we reflected finite and simple graphs and used general reference for graph-theoretic ideas in [10]. The graph G having the vertex-set V(G) and the edge-set E(G) is said to be a reverse edge-magic (REM) labelling then the one-to-one mapping
satisfying the property that there exists an integer k such that
for each edge xy in G. We call the reverse edge difference of edge xy, and k the reverse magic constant of graph G. In particular, if (V(G)) = {1,2, · , |V(G)|} then is called reverse super edge-magic labeling. A graph is called reverse(super) edge-magic if it admits any reverse (super) edge-magic labeling.
S Venkata ramana etal [10] introduced and studied the notion of reverse edge-magic graphs with a different name, i.e., graphs with reverse magic valuations, while the term of reverse super edge-magic graphs was firstly introduced by them. They showed that a star Sn+1 = K1, n is the only complete bipartite graph which is reverse super edge-magic total. They also showed that any odd cycle is reverse super edge-magic, but every wheel is not. Since then, some of authors have studied reverse(super) edge-magic properties in graphs, see, for instances, [ 8 ] and [9]. Figure 1 shows a reverse super edge-magic labeling on graph tree on 6 vertices with the reverse magic constant k = 2.
Let ? be an REM labeling on graph G(V,E). Let W ? V(G) ? E(G). Any restriction of ? to W is called a partial REM labeling on G. A partial REM labeling ? on graph G is a critical set if:
is the only reverse edge-magic labeling having ? as its partial REM labeling, and
No restriction of ? to any proper subset of W satisfies the property (i).
Let is an reverse edge-magic labeling on star Sn. According to [2], we build critical sets with size n, such that doesn’t include the center and its label and always consist of leaves and edges along with their labels. Here is the example of the above talk with n = 5, we have a reverse edge -magic labeling of S5 that is (S5) = {(1, 1), (2, 3), (3, 4), (4, 5), (5, 6), (6, 2), (7,8), (8, 9),(9,10), (10, 11), (11,7)}. Thus one of its critical sets is = {(2, 3), (8, 9),(9,10),(10,11), (11,7)}.
Hence we can conclude the necessary condition of the critical sets we built,are :
- (i) (1, a) with a is label of the center.
- (ii) (0, a) with a is any label of Sn.
- (iii) never include two equal ordinate and two equal axis.
- (iv) (a,b) (a + n, c) for any position a and a 1.
In the following section, we suggest two schemes for secret sharing based on crtical sets of a reverse super edge-magic labeling on a star Sn. The distribution and reconstruction algorithms in this schemes is calculated to work based on our knowledge of critical sets of reverse super edge-magic labeling, in specific on stars .
PROPOSED SCHEMES
Since the notion of secret sharing scheme introduced, various different types of secret sharing schemes have been proposed (by many authors). They used mathematical structures, such as vector spaces, polynomial, block design, room squares [5], and latin squares [7], to design secret sharing schemes. In this paper, we proposed two schemes for secret sharing based on edge-magic total labeling on graphs.
3.1 Supervisional Secret Sharing Scheme
In supermarkets or banks, when a cashier or teller wants to change or cancel an (important) transaction, on their computer, they will need their supervisor approval to do such a thing. The supervisor will enter a password and then the cashier or teller will complete the entry by his/her own password. In this situation, we can see that the supervisor has more power password then the cashier or teller.
Based on this situation, we build supervisional secret sharing scheme that will share a secret among one supervisor and set of customers under his/her supervision (staffs). In the following we propose an algorithm for this purpose.
Algorithm 3.1
- Distribution Algorithm
Input :
- · The length of bank manager’s share, n1 ( n1 even).
- · The length of bank employee’s share, n2 ( n2 even).
- · The number of bank employee, r.
Output :
- · The share for the bank manager’s, s0 ( s0 even)
- · The share for each bank employee (staff), pi for i =1,2, ·, r.
Steps:
- · Determine the size of star graph Sn used for the scheme, n = (n1+ n2)/2.
- · Build a reverse edge magic labelling on star Sn with the size n.
- · Set as a secret.
- · Select r distinct critical sets Q1, Q2· Qr of ? such that their intersection is a set S0= {(a1,b1), (a2,b2), · , (at,bt)}, where ai is the position of label bi under the labelling ? and t = n1/2.
- · Define , for i =1, 2·r.
Reconstruction Algorithm
Input:
- · The share of the bank manager, s0 ( s0 even)
- · The share of one of the staff, L.
- · The size of the star, n (kept by the system)
- Output: The secret is revealed or not.
Steps
· Define a set H = s0 ? L.
· If H is a critical set of ? then the secret is revealed otherwise the secret is not revealed.
In this scheme, the secret is reverse edge-magic labelling on graph Sn. The secret will be shared to a bank manager and his/her employee. The access structure ? in this scheme is the family of all sets of the form {s0, p}, where s0 is the bank manager and p is the staff.
3.2 Departmental Secret Sharing Scheme
In institutions with several departments, in some situation, to do an agreement, it will need some approval, those are from the head of the institution (Director) and one authorized faculty from each department. They give their approval by signing the agreement.
Based on this, we build departmental secret sharing scheme that will share a secret among one head of institution and several sets of authorized faculties. These sets represent the departments and the authorized participants be the authorized faculties.
Algorithm 3.2
Distribution Algorithm (with two departments)
Input :
- · The length of share for the director, n0 (n0 even).
- · The length of share for each authorized faculty in Department A, n1(n1 even).
- · The length of share for each authorized faculty in Department B, n2 ( n2 even).
- · The number of authorized faculties in Department A, r1.
- · The number of authorized faculties in Department B, r2.
Output:
- · The share for the director, s0 (s0 even).
- · The share for authorized faculty in Department A, SAi, for i = 1, 2·r1.
- · The share for authorized faculty in Department B, SBi, for i = 1, 2·r2.
Steps:
· Calculate the size of star graph Sn used in this scheme,n = (n0 + n1 + n2)/ 2
· Select, at random, an edge-magic total labelling ? on Sn.
· Set ? as a secret.
· Partition the edges of Sn into 3 sets: E(Sn) = S ? A ? B such that |S| = s0/2, |A| = n1/2 and |B| = n2/2.
· A restriction of any critical set of ? to S ? {all vertices incident to edge in S} can be chosen as s0.
· Select r1 restrictions of r1 non-isomorphic critical sets of ? to A?{all vertices incident to edge in A}. These restrictions will be used as shares SAi, for faculty in Department A.
· Select r2 restrictions of r2 non-isomorphic critical sets of ? on B ? { all vertices incident to edge in B}. These restrictions will be used as shares SBi, for faculty in Department B.
Reconstruction Algorithm
Input:
- · The share of one authorized faculty in Department A, SAi.
- · The share of one authorized faculty in Department B, SBj.
- · The share of the director s0.
- · The size of the star, n (kept by the system).
- Output : The secret is revealed or not.
Steps :
· Define a set H = s0 ? SAi? SBj
· If H forms a critical set of ? then the secret is revealed otherwise the secret is not revealed.
Algorithm 3.2 can be easily generalized for the use of more than two departments. This scheme works only if r1? 2s, where s = n1/2 and r2? 2t, where t = n2/2.
CONCLUSIONS
This paper proposed two level schemes of secret sharing based on reverse edge-magic labeling on graph G. In these methods, the secret is a chosen reverse edge-magic labeling, in particular, on star Snand tree . To distribute the shares, the algorithms work based on a reverse edge magic labeling. The reconstruction algorithms for these schemes are based on our knowledge on critical sets for stars .
Order an Essay Now & Get These Features For Free:
Turnitin Report
Formatting
Title Page
Citation
Outline
