Abstract. Secret sharing scheme is a strategy for data protection. Secret sharing is a method of how to distribute and share secret information (text, picture or image) among a group of N participants, so that we can recover the secret only by pre-designated sub-collections of participants. In the traditional secret sharing schemes, shared secret information can be revealed only with complex cryptographic computations. Various schemes have been proposed. However the size of the shares and implementation complexity of schemes increases when the number of participants increases. That is when a great number of participants are involved, the scheme will become impractical. In the traditional visual cryptography, shared secret information can be revealed from the shares without any cryptographic computations. The scheme uses only OR / XOR operations for reconstructing the secret information. In this paper we present a method to construct a special type K out of N access structure sharing scheme based on a number system called permutation ordered binary (POB) number system. This is an efficient way to hide secret information in different shares. Also the size of the shares is less than or equal to the size of the secret. This method recovers the secret image with original quality.
Keywords: secret sharing, Visual cryptography, Permutation ordered binary number system
Introduction
Secret sharing scheme is a method for distributing a secret amongst a group of participants, each of which is allocated a share of the secret. The secret can only be reconstructed when the shares are combined together; individual shares are of no use on their own. That is, in a secret sharing scheme there are one dealer and N players. The dealer gives a secret to the players, but only when specific conditions are fulfilled. The dealer accomplishes this by giving each player a share in such a way that any group of K (for threshold) or more players can together reconstruct the secret but no group of less than K players can. Such a system is called a (K, N)-threshold scheme [1]. Secret sharing was introduced by Shamir [1] in 1979.Shamir's solution is based on polynomial interpolation in finite sets. Various secret sharing schemes were proposed, but most of them need a lot of computations to decode the secret. In 1994, Naor and Shamir [2] introduced a new secret sharing scheme called visual cryptography scheme. Visual cryptography is a cryptographic technique which allows visual information (pictures, text, etc.) to be encrypted in such a way that the decryption can be performed by the human visual system, without the aid of computers. They demonstrated a visual secret sharing scheme, where an image was broken up into n shares so that only someone with all n shares could decrypt the image, while any n-1 shares revealed no information about the original image. Each share was printed on a separate transparency, and decryption was performed by overlaying the shares. When all n shares were overlaid, the original image would appear. The visual cryptography schemes works well only for black and images. This method doesn't work for color images. In 1987 Ito, Saito &Nishizeki introduced the idea of secret sharing for General Access Structures.Much research work happened to improve the quality of revealed image and to reduce the size of shares by many researchers including Atensie,Blundo,Santis,Atinson,Droste and many others[3],[4],[5],[6].They introduced graph access structure and a method to construct K out of N scheme using Minimal perfect hash function[5].
In 1997, Verheul and Van Tilburg [7] used the concept of arcs to construct a colored visual cryptography scheme. The concept for a c-color visual cryptography scheme is to transform one pixel to b subpixels and each subpixel is divided into c- color regions. In each subpixel, there is exactly one color region colored and all the others are black. The color of one pixel depends on the interrelations between the stacked subpixels. The major disadvantage is that the number of colors and number of subpixels determine the resolution of the recovered secret image.
Hwang and chang [8] proposed a scheme which improves the visual cryptography by assigning image to the transparency. This scheme saves mass computations to recover the secret image directly in human visual system. Unfortunately, this scheme works effectively in black and white images only. Based on modified visual cryptography [13], Chang, Tsai and Chen introduced a new secret color image sharing scheme.
The [9],[10],[11],[12] represents the different works done to improve the quality of images. The major disadvantages of these schemes are that the size of the share increases with the number of participants and the quality of recovered secret information is not to that of the secret information.
The following sections are thus arranged: the second section presents the permutation ordered number system and the algorithms related to N out of N threshold scheme; the third section describes in detail the proposed system; the fourth section discusses the findings; and finally come the conclusion.
Permutation Ordered Binary (POB) number system
This number system is introduced by A.Sreekumar and Dr.S.BabuSundar [14]. POB number system is defined with two non-negative integral parameters n and r. POB(n , r) system represent all decimal integers in the range [0,nCr-1].There exists two representation for each decimal integer
1) POB number: POB number is a binary string of length n with exactly r 1's
[bn-1 bn-2 ….b0].
2) POB value: it is calculated from POB number using the following formulae.
where
POB(9,4) system is used in this paper. There are 126 POB values with the range [0,125]. Smallest POB number is 000001111 (decimal value is 15 and POB value is 0C1 + 1C2 + 2C3 + 3C4 =0).Largest POB number is 111100000(decimal value =480 and POB value =8C4 + 7C3+ 6C2 + 5C1 = 70 + 35+15+5=125).
To represent a POB(9,4) number B , we need only7-bit POB value.ie the binary representation of POB value needs only 7 bits.
Eg: POB value of (001101010)p= 1C1+ 3C2+ 5C3+6C4 =1+3+10+15 =29.
N out of N threshold scheme using POB
Algorithm 1: POBnOutn(K)
[Sharing a secret among n blocks]
Input: A single byte string K = K1K2K3 . . .K8.
Output : n shares S1, S2, . . . , Sn of length 7 bit.
Step 1: Let A1,A2, . . .An be n 9 bit strings initialized to null(-1) bits.
Step 2: Randomly assign n-2 POB(9,4)-numbers one for each of Ai, 2 ≤ i ≤ n−1.
Step3: Let r be the quotient obtained, when, dividing POB value of the POB
number A2 by 14.
Step 4: The input string K is expanded to T by inserting one bit at position r.
Compute the binary string T = (T1T2 . . . T9) where
Step 5: Let W = T ⊕ A2⊕ A3⊕ . . . ⊕ An−1;
Step 6: noOfOne = 0;
Step7: let W = W1W2 . . .W9;
Step8: for i = 1 to 9 do
if (Wi = 1) then noOfOne = noOfOne + 1;
if (noOfOne is odd) A1i = 1 else A1i = 0;
Step 9: Randomly assign the rest null bits of A1 to 0 or 1.LetA1 consists of
Four 1s and five 0s.
Step 10: Compute An = W ⊕ A1;
Step 11: .For i = 1 to n do Si = POBValue(Ai).
Algorithm 2: POBValue(b)
[Find the POB value V(B) in decimal form of the 9 bit binary POB number
b= bn−1bn −2. . . b0]
Input: 9 bit binary POB number b= bn−1bn −2. . . b0
Output : POB value V(B) in decimal form.
Step1: Let p is a 9 bit long integer .Set all the bits of p to 0.
Step2: for j=0 to n-1
Step3: for j=0 to n-1 do position_value(j)=((j!)/[((j-pj)!)x pj!]);
Step4: POBValue=0;
Step5: for j =0 to n-1 do POBValue= POBValue +( b(j)x position_value(j));
Step6: V(B)= POBValue.
Algorithm3:Recover(p1, p2, …,pn)
[Recover the secret information]
Input: n POB numbers p1,…pn of the shares S1, . . ,Sn of length 7 bits each.
Output: The secret information K = K1K2K3 . . .K8.
Step 1: Let A1,A2, . .An be the POB-numbers corresponding to p1, p2, …,pn
respectively .ie for i=1 to n do Ai=POBNumber(pi);
Step2: r be the the quotient obtained, when, dividing p2 by 14.
Step3: Compute T = A1⊕ A2⊕ A3⊕ . . . ⊕ An. Let T = (T1T2 . . . T9).
Step 4: for i = 1 to 8 do
if (i ≥ r) j = i + 1;else j = i;
Ki = Tj ;
Step 3.The recovered secret is K = K1K2K3 . . .K8.
Algorithm 4:POBNumber(value)
[Generate POB-number corresponding to a given POB-value. In a POB(n, r) number system, if a POB Value, value is given, the algorithm generates POB(n,r) number B such that V (B) = value.]
Input : Three numbers: n, r and value with r ≤ n and 0 ≤ value ≤(nCr)-1
Output: The POB-number B = bn−1bn−2 . . . b0.
Step 1: Let j = n and temp = value.
Step 2: for k = r down to 1 do:
Repeat {
j = j − 1;
p =jCk;
if (temp ≥ p) temp = temp − p; bj = 1; else bj = 0;
} Until (bj = 1);
Step 3: if (j > 0)
for k = j − 1 down to 0 do bk = 0;
step4: B = bn−1bn−2 . . . b0 is the POB-number.
K out of N threshold Scheme Construction (Proposed System)
In the general K out of N threshold scheme, every combination of k or more participants can recover the secret, but every group of less than k participants cannot obtain any information about the secret. In this proposed system there is a change in the definition of K out of N Scheme.
Definition: In the proposed K out of N threshold scheme the N participants are divided into (K-1)major participants and (N-K+1) minor participants. In this scheme,every combination of major participants with atleast one minor participants can recover the secret, but every group of atleast the absence of one major participants and absenceof allminor participants cannot obtain any information about the secret.
Example: Consider 3 out of 5 threshold schemes. Let the participants P={1,2,3,4,5},Major participants={2,4}and minor participants={1,3,5}. So the family of qualified sets is{{1,2,4},{2,3,4},{2,4,5},{1,2,3,4},{1,2,4,5},{2,3,4,5},{1,2,3,4,5}}.
Algorithm 5: Distribute(IMAGE,K,N)
Input: secret color image IMAGE,threshold K andnumber of Participants N.
Ouput: N share images for the participants.
Step1: Read the color image IMAGE to the three dimensional matrix I. Let the
order of I be mXnXc.Each element of I is an integer value in the range [0,255].
Step2: Convert I into three components R,G and B. Size of each component is
mXn.
Step3: Represent R,G and B components in binary form as Binary_Red,
Binary_Green and Binary_Blue respectively.ie represent each element in 8
bit form. So each component is a matrix of order mX(8n).
Step4: Generate K shares each for Binary_Red,Binary_Green and Binary_Blue
using the algorithm POBnOutn. Let the shares be (,,..)
.The size of each share is mX(7n).
Step5: Convert each contiguous eight elements of shares into its decimal form. So
the shares becomes (,,..)
with size m X ceil(7n/8).
Step6: Combine the corresponding R,G and B components of shares into a single
one. Let the combined shares be share1, share2,…., shareK. Size of share is
mX ceil(7n/8)X3.
Step7: Generate (K-1) major participants randomly.
Step8: Assign first (K-1) shares to the major participants and assign the remaining
share shareK to all the minor participants.
Algorithm6: Reconstruct(p1, p2, …,pL)
[Reconstruct the secret color image]
Input: L participants p1,…pL with their share images S1, . . ,SL.
Output: The secret image IMAGE.
Step1: Convert each shares into R,G and B components say (,,..),
.
Step2: Represent each element of (,,..) in 8 bit binary form. The shares be
represented as (,,..).
Step3: Compare the first seven bits (elements) of (,,..) and select
only the participants with distinct shares .Let the participants are q1,q2,…qm.
Step4: Represent each element of (,,..),
in 8 bit binary form. The shares be represented as
(,,..), .
Step5: Apply algorithm 3 for each contiguous seven bits on the shares
(,,..) then on each contiguous seven bits on the shares
and on .The resultant is
represented as qR,qG and qB respectively.
Step6: Convert the continuous 8 bits of qR,qG and qB to its decimal form and it is
represented as R,G and B.
Step7: combine the R, G and B components into IMAGE.
Experimental Results and Discussions
Experimental results are presented to illustrate the effects of our proposed system. All images in our experiment contain red, green, blue components.
Consider 3 Out of 5 schemes. Participants={1,2,3,4,5}
Major Participants={2,4} ,Minor Participants={1,3,5}
Qualified sets={{1,2,4},{2,3,4},{2,4,5},{1,2,3,4},{1,2,4,5},{2,3,4,5},{1,2,3,4,5}}.
Fig. 1. Secret image: 176X175 Fig. 2. Share1:176X154
Fig. 3. Share2:176X154 Fig. 4. Share3:176X154
Fig. 5. Share4: 176X154 Fig. 6. Share5: 176X15
Fig.7. Share2+Share4+atleast one of the Fig.8. Share1+Share2+Share3(one major
Shares Share1, Share3 and share5 share is missing)
Fig.9. Share1+Share3(All major shares are missing).
Conclusion
