Identification & Detection of Intruder in Secret sharing system
Authors
Kahkashan Siddavatam
Professor – Lokmanya Tilak college of Engineering, Navi Mumbai.
Email ID -
Poonam Yadav
Lecturer – Ramrao Adik College of Engineering Navi Mumbai
Email ID–
Contact No - 09766538251
Abstract
Network security is very important to protect confidential documents against misuse of the system. There are a number of drawbacks that can arise if network security is not launched properly, some of which include Violation of Confidentiality, Damaging Data, and Manipulation of Data. Apart from the disadvantages mentioned, there are many more potential threats that can cripple a system. Cryptography plays an important role in data security and network security also, but again there is issue of security of secret keys. Secrete sharing can be right answer to this particular question in addition to this it can be applied in many real time applications for security concern.
This paper basically focuses on secret sharing for data and images. Section 2 gives details of share construction, Share distribution, secret reconstructions and identification and detection of cheaters. Next sections gives the algorithms for secrete sharing for data as well as images. Last section does the result analysis for the same.
1.Introduction
Now days there are many issues in secret sharing one of them is to identify and detection of cheater.
In 1979, Shamir and Blakley first developed the concept of the (t,n) threshold secret sharing scheme. Then Naorand Shamir extended the secret sharing concept into image research, and referred it as image secret sharing in 1994. After Shamir, many secret sharing schemes have been proposed for processing 256 gray-level images. But in these schemes, shadow images have larger image sizes compared to that of the original secret image.
The scheme given in this paper is being an extension of Shamir’s (t, n)-SS scheme, cheater detection and identification are very important to achieve fair reconstruction of secret. Assuming that there are more than t shares (i.e. it only requires t shares) for reconstructing the secret, the redundant shares (j shares) can be utilized for cheater detection and identification. Based on this background this work describes the approach and proposal to detect and identify the cheaters in data and image. One unique feature of the proposed scheme is that, the same share which is used for secret reconstruction is utilized to detect and identify the cheaters.
- Selected Methodology
The scheme being an extension of Shamir’s (t, n)-SS scheme, cheater detection and identification are very important to achieve fair reconstruction of secret. Assuming that there are more than t shares (i.e. it only requires t shares) for reconstructing the secret, the redundant shares (j shares) can be utilized for cheater detection and identification. Based on this background this work describes the approach and proposal to detect and identify the cheaters. One unique feature of the proposed scheme is that, the same share which is used for secret reconstruction is utilized to detect and identify the cheaters. The scheme uses the shares generated by the dealer to reconstruct the secret and at the same time to detect and identify the cheaters.
2.1 Modules
There are four modules of the system;
- Share creation
- Shares Distribution Phase
- Secret Reconstruction Phase
- Identification And Detection of Cheaters
2.1.1 Share Creation
During this phase, a trusted entity, usually called the share builder, is supplied with required input to produce a share for each shareholder. It requires the fowling information:
The secret: can be as small as an encryption key, a safe combination or as large as a database.
Without losing generality, usually the secret information is represented as integers.
1)The trusted participants (shareholders): the people/machines that will be given shares of the secret to keep.
2)The qualified subsets (access structure): A qualified subset is a subset of the shareholders that should be able to rebuild the secret.
In this stage the end user can create share and combine the images. The procedure is as follows:
1)Browsed the file you want to create, apply the qualified set threshold (k) and enter the number of participant (m) required and save on the server.
2)Share are created successfully
2.1.2 Shares Distribution Phase
In shares distribution phase, the shares produced in the first phase are delivered to the shareholders as shown in figure 7. In some schemes, however, methods to distribute shares over public channels were proposed but in the proposed work will be distribution it on LAN system.
2.1.3 Secret Reconstruction Phase
During Secret reconstruction phase, a qualified subset of shareholders will pool their shares to a trusted entity, usually called secret-builder, to reconstruct the secret (Figure 8). Reconstructing the secret needs to be secure. All shares should be submitted to secret-builder over secure channels to insure privacy. As mentioned in share distribution phase, public channels have been used to transfer shares to the secret-builder.
Share Combine
- Enter the qualified set threshold (t).
- Enter the number of participant (n).
- Select the qualified set required.
- Proper selection of the qualified set will give a secret.
2.1.4 Identification and Detection of Cheaters
Algorithm for cheater detection and identification:
This work represents the approach and proposal to detect and identify the cheaters. One unique feature of the proposed scheme is that, the same share which is used for secret reconstruction is utilized to detect and identify the cheaters. The scheme uses the shares generated by the dealer to reconstruct the secret and at the same time to detect and identify the cheaters.
Method for detecting cheaters
In Shamir’s (t, n)-SS scheme, a t − 1 degree interpolating polynomial can be uniquely reconstructed based on t shares. Thus, if there are more than tshares and there is no faked share, according to definition of a consistent polynomial should be reconstructed for all combinations of t shares. Cheater detection is determined by detecting inconsistent polynomials (or secrets) among all reconstructed secrets. However, cheaters can collaborate to determine their faked shares to fool honest shareholders to believe that a faked secret is a real secret. Proposed detecting scheme under three attacks as presented.
Method for identifying cheaters
When cheaters have been detected, there are inconsistent reconstructed polynomials (or secrets) for all combinations of t shares. Among all reconstructed secrets, if the appropriate secret is the majority of secrets as defined in above chapter, then the majority voting mechanism to identify each faked share can be used. For this one need to investigate conditions that the appropriate secret is the majority of secrets. Additionally bounds of identifiability of the proposed identifying scheme under three attacks are presented.
Let c denote the number of faked shares and j (n ≥ j ≥ t) to denote the number of participants in a secret reconstruction. There are j −c legitimate shares in a secret reconstruction. One can use J = {i1, . . . ,i j} ⊆ {1, . . . , n} to denote all participants, T = {T1, . . . , tu}to denote all subsets with t participants of J where u =H to denote the set of the honest participants, and C to denote the set of the cheaters. The proposed scheme consists of the following algorithms.
3.Mathematical Model for Share Generation:
This algorithm is same as that of Shamir’s scheme as implemented in project stage-1
3.1 Steps for share generation algorithm:
a.Share Generation Using Shamir’s Scheme:
Based on Lagrange interpolation polynomial Also called Lagrange interpolation scheme
Choose a large prime p, the message M is represented as a number (mod p)
S (x) ≡M+s1x+s2x2+…+st-1xt-1 (mod p) ………………(1)
(xi,yi), i=1,2, …, w; yi= s(xi) (mod p)…………………(2)
b.Calculate Lagrange Interpolating Polynomials
Suppose that the function y=f(x) is known at the n+1 points (x0,y0), (x1,y1), … (xn..yn), where a≤ x0 <x1 <x2 …<xn≤b, then there is a polynomial Pn(xi)=yi, 0≤i≤n
c.Computing Secret Value M:
………………….(3)
………...………. (4)
d.Secret) Value Sharing:
A ( t, n) threshold secret sharing should satisfy the following requirements:
- A secret value M is used to generate n shadows.
- Any ≧t shadows can reconstruct the secret value M.
- Any ＜t shadows cannot get sufficient information to reveal the secret value M.
- A (t, n) threshold polynomial can be written by s(x) ≡ M+s1x+s2x2+…+sk-1xk-1 (mod p)
- Select n distinct integer x1,x2,…,xn form [0,p-1]
- Deliver (xi,s(xi)) to the i-th participant
p= a (large) prime number
M: secret value
s1,…,sk-1: randomly chosen from [0, p-1]
- To reveal the secret value M, one must collect (at least k) ≧t shadows.
- Without loss of generality, use (x1,s(x1)),…, (xk,s(xk)) as t shadows.
- One can reveal the secret value M by using Lagrange interpolation.
………………………(5)
where M=s(0)
e.Secret Image Sharing
A (t, n)-threshold secret image or message sharing must satisfy the following requirements:
- (1)The secret image S is used to generate n shadow images or message.
- (2)Any ≧t shadow images can reconstruct the secret image or message.
- (3)Any ＜t shadow images cannot get sufficient information to reveal the secret image or message.
- Secret Image/Message Reconstruction:
- Without loss of generality, one have (x1,s(x1)),(x2,s(x2)),…, (xk,s(xk)).
- Use Lagrange interpolation to reconstruct the imageor message
S1 / S2 / Sk / Secret Reconstruction
…. /
Figure 9Generation of shadow images/Message
g.Shadow Images Acquisition
- The equation can be written by g(x)≡a0+a1x+a2x2+…+ak-1xk-1 mod 251
- Select n distinct secret keys x1,x2,…,xn.
- Deliver (xi,s(xi)) to the ith participant.
3.2 Mathematical Model for Secret Reconstruction Algorithm:
This algorithm consists of following two sub-algorithms for cheater detection and cheater identification respectively.
Algorithm 1 (Cheater detection)
Input: t, n, J ,si1, . . . , si j
1. Compute an interpolated polynomial f (x) of j points (i1 , si1), . . . , (i j, si j ).Set the degree of f (x) to be d.
2. If d = t − 1, then s = f (0), and
Output: There is no cheater and Secret is s ; otherwise
Output: There are cheaters.
Algorithm 2 (Cheater identification)
1. For all Ti ∈T, compute si= F(Ti ) where i= 1, . . . , u.
2. DivideU= {s1, . . . ,su} into v subsets Uisuch that U = U1∪···∪UvwhereUk∩Ul= ∅for 1 ≤k, l vandk _= l, and Ui= {si1, . . . , siwi} whereswi=si1 = ··· =siwi.
3. Set wz= maxi {wi}, and set s = swz.
4. PickTk∈Tsuch that s = F(Tk) = FTk (sik1, . . . , sikt ), and set R = J −{ik1, . . . , ikt}.
5. Pickir∈Rorderly and remove it from R, and compute s r=F(sir , sik2, . . . ,sikt ).
6. If sr= s, then put irintoH; otherwise put irintoC.
7. Return Step 5 until R = ∅.
Output: The cheater set is C.
4.Attacks and analysis:
For proposed scheme following three attacks are consider:
4.1 Type 1 attack
The cheaters of this type attack can be either honest shareholders who present their shares in error accidentally or dishonest shareholders who present their faked shares without any collaboration. Each faked share of this attack is just a random integer and is completely independent with other shares.
Analysis for attack 1:
Under type 1 attack, proposed scheme can detect cheaters if j ≥ t +1, and identify cheaters if j − c > t.
4.2 Type 2 attack
Under type 2 attack, the proposed scheme can detect cheaters if {(c < t)∩( j ≥ t +1)} ∪ {(c ≥ t)∩( j −c ≥ t)}, and identify cheaters if {(c < t)∩( j −c ≥ t +1)} ∪ {(c ≥ t) ∩ ( j − c > c + t − )}.
4.3 Type 3 attack
Under type 3 attack, the proposed scheme can detect cheaters if j −c ≥ t, and identify cheaters if { j≥ t + 1} ∩ {j − c > c + t − 1}.
5.Result Analysis
In a (t, n) secret sharing scheme, a secret s is divided into n shares and shared among a set of n shareholders by a mutually trusted dealer in such a way that any t or more than t shares will be able to reconstruct this secret; but fewer than t shares cannot know any information about the secret. When shareholders present their shares in the secret reconstruction phase, dishonest shareholder(s) (i.e. cheater(s)) can always exclusively derive the secret by presenting faked share(s) and thus the other honest shareholders get nothing but a faked secret. Cheater detection and identification are very important to achieve fair reconstruction of a secret. Considering the situation that there are more than t shareholders participated in the secret reconstruction. Since there are more than t shares (i.e. it only requires t shares) for reconstructing the secret, the redundant shares can be used for cheater detection and identification. The proposed scheme uses the shares generated by the dealer to reconstruct the secret and, at the same time, to detect and identify cheaters.
The proposed scheme is based on threshold secret sharing. It is an extension of Shamir’s scheme. In Shamir’s scheme one can create shares but at the time of combining it’s not guarantee that one can reconstruct original secret because it cannot find out cheater in secret sharing scheme, but on the proposed scheme one can find out the cheater by using single algorithm.
Means the cheater are greater than threshold in that case one cannot find the cheater but in proposed scheme by taking redundant share(j) which is use to identify and detect and cheater condition of propose scheme is(t <j<n).
The proposed scheme in this work provide single share that are used for share both and the time complexity of algorithm is 0(j!). The detection and identification done under three attacks and can plot number of maximum cheater. The detectability of our proposed scheme decreases gradually from type 1 to type 3 for participants j = 5. And the dentifiability of proposed scheme decreases gradually from type 1 to type 3 for participants j = 9. The decrement of detectability and identifiability from type 1 attack to type 3 attack is caused by the increment of attackers ability from type 1 attack to type 3 attack. In following Figure , it illustrates that detectability of proposed scheme is in proportion to the number of participants.
Figure Histogram for type -1 Attack
In above Figure Histogram for type -1 Attackgraph is plot with the help of histogram. It is shares (j) vs. cheater .maximum no of cheater can be plot that are detected in cheater set first detection of charter is find out then it can be plot the cheater by substituting the value of shares(j,n.t) check for type 1,type 2,and type 3.the above figure is for type 1
Figure: Histogram for type- 2 Attack
In above figure graphis plot for type 2 according to the condition of type 2 attacks there is minor difference between type 1 and type 2 attacks. It is more difficult to detect the cheater in type 2 than type 1
Figure: Histogram for type- 3 Attack
In abovefiguregraph is plot for type 3 attack for the detection of cheater. It is no. of shares vs cheater (c max) in type 3 it is more difficult to identify cheater than type 1 and type 2.
The decrement of detectability and identifiability from type 1 attack
to type 3 attack is caused by the increment of attackers ability from type 1 attack to type 3 attack.
References
[1] A.Shamir, “How to share a secret”.
Communication of the ACM, 1979,
22(11),pp.612-613.
[2] G.Blakley, “Safeguarding cryptographic keys”,
Proc. AFIPS 1979. Natl. Conf., New York, 1979,
pp. 313-317.
[3] E.F.Brickell, D.M.Daveport, “On the classification
of idea secret sharing scheme”, J.Cryptology,
1991, 4(2), pp.123-134.
[4] P.A.Fouque, G.Poupard, J.Stern, “Sharing
decryption in the context of voting or lotteries”,
Proceeding of Financial Cryptography 2000,
Berlin:Springer Verlag, 2000, pp. 90-94.
[5] Chor B, Goldwasser S, Micali S, Awerbuch B,
“Verifiable secret sharing and achieving
simultaneity in the presence of faults”, Proceeding
of 26th IEEE Symposium on Foundations of
Computer Science, 1985, pp.383-395.
[6] Feldman A, “A practical scheme for noninteractive
verifiable secret sharing”, Proceedings
of 28th IEEE symposium on Foundations of
Computer Science, 1987, pp.427-437.
[7] Pedersen T P, “Non-interactive and information
theoretic secure verifiable secret sharing”,
CRYPTO’91, 1991, pp.129-139.
[8] W.-A,Jackson, K.M.Martin, C.M.O’keefe, “On
sharing many secrets”, Asiacrypt’94, 1994, pp.42-
54.
[9] J.He, E.Dawson, “Multistage secret sharing based
on one-way function”, Electronics Letters, 1994,
30(19), pp.1591-1592.
[10] J.He, E.Dawson, “Multi-secret sharing scheme
based on one-way function”, Electronics Letters,
1995, 31(2), pp.93-95.
[11] L. Harn. “Comment: Multistage secret sharing
based on one-way function”. Electronics Letters,
31(4):262, 1995.
[12] H.-Y.Chien, J.-K.Jan, Y.-M.Tseng, “A practical
(t,n) multi-secret sharing scheme”, IEICE
Transactions on Fundamentals, 2000, E83-(12),
pp.2672-2675.
[13] Chou-Chen Yang, Ting-Yi Chang, Min-Shiang
Hwang, “A (t,n) multi-secret sharing scheme”,
Applied Mathematics and Computation, 2004,
151, pp. 483-490.
[14] Liao-jun Pang,Yu-Min Wang, “A new (t,n) multisecret
sharing scheme based on Shamir’s secret
sharing”, Applied Mathematics and Computation,
2005, 167, pp. 840-848.
[15] T.ElGama, “A public-key cryptosystem and a
signature scheme based on discrete logarithms”,
IEEE Transactions on Information Theory,
1985,IF-31(July), pp.469-472.
[16] R.L.Rivest, A.Shamir, L.Adleman, “A method forbtaining digital signatures and public key
cryptosystems”, Communications of the ACM,
1978,21(February), pp.120-126.