PDF Archive

Easily share your PDF documents with your contacts, on the Web and Social Networks.

Share a file Manage my documents Convert Recover PDF Search Help Contact



48I14 IJAET0514343 v6 iss2 987to994 .pdf


Original filename: 48I14-IJAET0514343_v6_iss2_987to994.pdf
Author: "Editor IJAET" <editor@ijaet.org>

This PDF 1.5 document has been generated by Microsoft® Word 2013, and has been sent on pdf-archive.com on 13/05/2013 at 13:25, from IP address 117.211.x.x. The current document download page has been viewed 660 times.
File size: 664 KB (8 pages).
Privacy: public file




Download original PDF file









Document preview


International Journal of Advances in Engineering &amp; Technology, May 2013.
©IJAET
ISSN: 2231-1963

REVISITING PROACTIVE SECRET SHARING BASED ON
SHAMIR’S SCHEME
Sonali Patil1, Nikita Rana2, Dhara Patel2, Prajol Hodge2
1

Assistant Professor, Computer Department PCCOE, Pune, India
2
BE Student, Computer Department PCCOE, Pune, India

ABSTRACT
The Secret Sharing scheme assumes long-lived shares. However the protection provided for such long lived and
sensitive shares may be insufficient. The security in a system that is exposed to attacks and break-ins might
become exhausted. The goal of the pro-active security scheme is to prevent the adversary from learning the
secret or from destroying it. The Shamir’s Secret Sharing is pioneer method for secret sharing. Due to its
security in information theoretic sense compare to many secret sharing methods researchers found it more
useful and interesting. In this paper a novel proactive secret sharing scheme for image is proposed based on
Shamir’s secret sharing. The proposed schemes provides the extended capabilities for proactiveness like adding
new shareholder, removing shareholder and renewing shares and recover lost or corrupted shares.

KEYWORDS: Secret Sharing, Visual Cryptography, Proactive Secret Sharing, Extended Capabilities

I.

INTRODUCTION

1.1 Secret Sharing[1]
The idea of secret sharing is to divide a secret into pieces called shares, which are then distributed
amongst shareholders by the dealer. This scheme is usually implemented for gaining collective trust
instead of individual trust in which part of secret is provided to the each person in the group of n
persons. Out of this group, minimum k persons with their share will be required to reconstruct original
secret. There are many practical applications of secret sharing schemes. For example, to transfer
money from a bank a manager and a clerk need to cooperate, a ballistic missile should be launched
only if three officers authorize the action. In this way the authority to begin an action, for example the
launch of a missile is divided for the purpose of greater security. Shamir [2] embarked the concept of
secret sharing using langrage’s interpolation.
Properties of Shamir’s Secret Sharing [2]
 Perfect Security –Given any k shares, the polynomial is uniquely determined. However, k-1 or
fewer shares, do not supply any further information regarding the secret.
 Ideal – Each share is exactly the same size as the secret
 Extendable – additional shares may easily be created, simply by calculating the polynomial in
additional points.
 Flexible – can assign different weights to different authorities.
 Homomorphic property: Shamir’s secret sharing (SSS) scheme has the (+, +) homomorphism
property.
 Efficient Distributed Mechanism for Arithmetic Calculations.

1.2 Proactive Secret Sharing[3][4]
Proactive secret sharing scheme (PSSS) was introduced to improve security through periodic
executions. With no PSSS, using an (k, n) threshold secret sharing scheme, SSS can tolerate up to k-1

987

Vol. 6, Issue 2, pp. 987-994

International Journal of Advances in Engineering &amp; Technology, May 2013.
©IJAET
ISSN: 2231-1963
compromised shares. Given enough time, a hacker may be able to compromise enough shares (k or
more) to gain the secret. PSSS is a scheme that allows generating new set of shares for the same secret
from the old shares without reconstructing the secret. Using PSSS, all the shares are refreshed so that
old shares become useless. Thus, an adversary has to gather at least k shares between two executions
of PSSS. The secret remains confidential if fewer than k shares were compromised from the start of
one PSSS to the end of the next PSSS.
The goal of the pro-active security scheme is to prevent the adversary from learning the secret or from
destroying it, In particular any group of k non-faulty shareholders should be able to reconstruct the
secret whenever it is necessary. The term proactive means the fact that it's not necessary for a
violation of security to occur before secrets are refreshed, the refreshment is done periodically and
hence, proactively.
The core properties of pro-active secret sharing:
 To renew existing shares without changing the secret, so that previous exposures of shares
will not damage the secret.
 To recover lost or corrupted shares without compromising the secrecy of the shares.
 Reconstruction of Lost / Corrupted Shares

1.3 Limitations
There are some limitations regarding secret sharing which include the dominance of type of hacker
and type of attacks.
Active &amp; Passive attacks
A secret sharing system is still quite vulnerable when a dynamic adversary determines to break into
the system before the lifetime of the secret expires. Ben-Or et al. [5] discussed a general theory for the
distributed fault tolerance systems and presented some possible solutions to avoid such attacks.
Among many different classifications of adversary attacks, one of the most notable ones is to classify
the attacks as:
 Passive adversary attacks
 Active adversary attacks.
Where passive adversary attacks are primarily resulting in spoofing data without modification or
corruption to the data. In contrast to the passive adversary attacks, the active adversary attacks are
much more malicious wherein the adversaries can persistently attempt to infiltrate a system, and/or to
damage or destroy data already stored in the system.
The rest of the paper is organized as follow. Section 2 contains literature survey of few proactive
secret sharing schemes. Section 3 covers proposed proactive secret sharing schemes based on
Shamir’s secret sharing. It describes implementation algorithms for Construction, Reconstruction,
Enrollment, Disenrollment, Renewal and Recovery of Lost/Corrupted shares. Section 4 shows
implementation results on proposed scheme. Finally in section 5, we summarize the proposed scheme
based on algorithms and results.

II.

LITERATURE SURVEY

2.1 Herzberg’s [6] Proactive Secret Sharing scheme
Herzberg [6] proposed the PSS scheme based on the Shamir SSS [2] to address the problem of passive
and active attacks. This method periodically renews the shares (without reconstructing the secret) so
that it prevents an adversary from gaining the knowledge of the secret before it expires. To counter
active adversary attacks, Herzberg et al. combined the ideas of the VSS technique to prevent dishonest
participants (or compromised participants by active adversaries) from refusing to change the shares
during the renewal process, or launch invalid secret shares.
To periodically update shares is an effective way to protect a secret from being revealed by adversary
attacks. Herzberg et al. developed a PSS technique for the Shamir’s method. When Shamir’s SSS is
initialised, at the beginning of every time period, all ‘honest’ servers can trigger an update phase in
which the servers perform a share renewal protocol. The shares computed in period t are denoted by
using the superscript t, i.e., (xi, f t (xi )), t = 0, 1, . . . . We know that the secret d0 at time (t− 1) is

988

Vol. 6, Issue 2, pp. 987-994

International Journal of Advances in Engineering &amp; Technology, May 2013.
©IJAET
ISSN: 2231-1963
d0 = f (t−1) (0).
The algorithm is to construct a new (k − 1) random polynomial function at each updating phase as,
δ(x) = a0 + a1 x + a2 x 2 + … + ak−1 x k−1 (mod p),
(1)
where δ(0) = 0 so that f t (0) = f t−1 (0) + δ(0) = d0 + 0 = d0 .
Since the δ(x) function does not have a constant term, consequently, any group of k or more servers
can still compute d0 by contributing their new shares. However, a combination of k shares using past
and present shares cannot be used to reconstruct the secret. As a result, the secret is protected from
being revealed by the passive adversaries.

2.2 Proactive Secret Sharing Scheme using matrix projection [7]
Lie Bai [8] proposed a secret sharing scheme for images. Lie Bai and Zou [7] proposed a secret
sharing scheme which supports proactive secret sharing with enrollment, disenrollment, and periodic
renewal of shares. There is no need to expose the secret and other shares while providing a new share
to new enrolled shareholder. Also he introduced a new, secure and distributed proactive secrete
sharing scheme using the matrix projection method. This scheme is different than Hertzberg’s
scheme. After the shares are updated, any k shares of past and present shares cannot be used to reveal
the secret matrix. This method looks after the protection against the passive attacks.
Some other methods are recently published for proactive secret sharing scheme [9][10][11].
The proposed Proactive secret sharing for images based on Shamir secret sharing[2] and Thin-Lin’s
[12]method.

2.3 Thien and Lin’s Image Secret Sharing Scheme[12]
Thien and Lin [12] proposed a (k, n) threshold-based image SSS by cleverly using Shamir’s SSS [2]
to generate image shares. The essential idea is to use a polynomial function of order (k − 1) to
construct n image shares from an l × l pixels secret image (denoted as I) as,
Sx(i, j) = I(ik + 1, j) + I(ik + 2, j)x . . . +I(ik + k, j)xk−1 (mod p)
where 0 ≤ i ≤ ( l/ k) and 1 ≤ j ≤ l. This method reduces the size of image shares to become 1/k of the
size of the secret image. Any k image shares are able to reconstruct every pixel value in the secret
image.

Fig 1. Secret Sharing Process for Lena Image [12]

III.

PROPOSED SCHEME

3.1 Proactive Secret Sharing based on Shamir’s Secret Sharing:
The proposed SSS Scheme is a threshold scheme based on polynomial interpolation. It allows a dealer
D to distribute a secret value s to n shareholders, such that at least k shareholders are required to
reconstruct the secret using SSS. The protocol is information theoretically secure, i.e., any fewer than
k shareholders cannot gain any information about the secret by themselves.

989

Vol. 6, Issue 2, pp. 987-994

International Journal of Advances in Engineering &amp; Technology, May 2013.
©IJAET
ISSN: 2231-1963
1. Construction
To share the secret image among shareholder such that k shareholder are required to reconstruct the
secret.
i.
Dealer D generates a polynomials f(x) of degree k-1 by taking the pixel values of secret image
as as d0 , d1 , d2 .... dk−1 .
f(x) = d0 + d1 x + d2 x 2 + .. + dk−1 x k−1 (mod p)
ii.

The image shares are constructed by using the value of f(x) generated for all pixel values of
original secret image

iii.

Dealer destroys secret image and generated f(x) functions.

iv.

Each i’th shareholder will get a image share.

2. Reconstruction
To reconstruct the secret image pixel from any k image shares out of n image shares
i.

Dealer asks shareholders to submit their image shares.

ii.

Dealer uses Shamir’s Lagrange interpolation formula to get the original secret image s.

3. Enrollment of Shareholder
Enrollment of shareholder consists of adding a new person in the k trusted group of shareholders.
i.
Dealer D generates polynomial f(x) of degree k-1 using Lagrange’s interpolation by taking
the minimum k image shares from the shareholders.
ii.

Dealer decides new shareholder number i and creates new image share by computing f(i) to
get image share i and deliver to the new i’th shareholder .

4. Disenrollment of Shareholder
Disenrollment of shareholder consists of removing an untrusted person from the k trusted group of
shareholders to make secret more secure.
i.
Dealer takes a note for not to consider the i’th shareholder which has to be removed.
ii.

It is not affecting on other shareholders shares.

5. Renewal of Shares
The purpose here is to renew the image shares periodically. We assume an initial stage where a secret
s is encoded into n image shares using Shamir’s secret sharing scheme. After some specific time
period Dealer will generate and distribute new image shares by taking old image shares from
participants.
i.
Dealer will generate a polynomial Pi(X) of degree k-1 .
ii.

Dealer will ask to share existing image shares f(i) from all shareholders.

iii.

Dealer computes new image share by adding old image share- f(i) to the sum of the new n
image shares. Mathematically speaking:

h(i)  f (i)  c1 Pc (i)
n

iv.

Dealer distributes new image share h(i) to each shareholder i

6. Detection of Corrupted Share
i.

Dealer will ask all shareholders to share their image shares.

ii.

Dealer will make all combinations of k groups of received shares.

iii.

Dealer will compute secret from those groups.

iv.

After analyzing wrong secret generated groups dealer will come to know about corrupted
share.

990

Vol. 6, Issue 2, pp. 987-994

International Journal of Advances in Engineering &amp; Technology, May 2013.
©IJAET
ISSN: 2231-1963
Limitation: If more number of shares are corrupted this approach will not work. No of corrupted
shares is limited upto n-k.

7. Reconstruction of Lost/Corrupted Share
From correct received shares in the above step Dealer will generate new image share for the corrupted
shares shareholder.

IV.

RESULTS

4.1 Home Window

Fig.2 Main Window

4.2 Construction of Shares

Fig3.Construction of Shares

991

Vol. 6, Issue 2, pp. 987-994

International Journal of Advances in Engineering &amp; Technology, May 2013.
©IJAET
ISSN: 2231-1963
4.3

Reconstruction of Secret

Fig 4. Reconstruction of Secret

4.4 Enrollment of shareholder

Fig5. Enrollment of shareholder

4.5 Renewal of Share

Fig 6. Renewal of Shares

992

Vol. 6, Issue 2, pp. 987-994

International Journal of Advances in Engineering &amp; Technology, May 2013.
©IJAET
ISSN: 2231-1963
4.6 Disenrollment of shareholder

Fig 7. Disenrollment of shareholder

4.7 Recovery of Lost/Corrupted Share

Fig 8 Recovery of Lost/ Corrupted Shares

V.

CONCLUSION

The proposed implemented proactive secret sharing based on Shamir’s scheme supports the extended
capabilities like enrolling new shareholder in the system, dis-enrolling the shareholder, periodically
renewing shares and detecting lost and corrupted share to the existing secret sharing scheme. The
proposed method is simple, less complex compared to existing methods.

VI.

FUTURE SCOPE

The scheme can be modified for better time complexity without Dealers interference and to handle
active attacks in near future. Along with this cheater identification using verifiable secret sharing can
be added in proactive secret sharing.

993

Vol. 6, Issue 2, pp. 987-994

International Journal of Advances in Engineering &amp; Technology, May 2013.
©IJAET
ISSN: 2231-1963

REFERENCES
[1] R. Stinson, “Cryptography: Theory and Practice”, CRC Press, Boca Raton 1995.
[2] Shamir, A., “How to Share a Secret”, Communications of the ACM, vol.22, no.11, 1979.
[3] Sonali Patil and Prashant Deshmukh. “An Explication of Multifarious Secret Sharing Schemes.”
International Journal of Computer Applications 46(19):5-10, May 2012
[4] Sonali Patil. Nikita Rana. Dhara Patel. Prajol Hodge. “Analyzing Proactive Secret Sharing Schemes”,
International Journal of Engineering Research &amp; Technology (IJERT),ISSN: 2278-0181,Vol. 1 Issue 7,
September – 2012.
[5] Ben-Or, M., Goldwasser, S. and Wigderson, A. (1988) ‘Completeness theorems for non-cryptographic
faulttolerant distributed computation’, Proceedings of the Twentieth Annual ACM Symposium on Theory
of Computing, 2–4 May, Chicago, Illinois, pp.1–10.
[6] Herzberg, A., Jarecki, S., Krawczyk, H. and Yung, M. (1995) ‘Proactive secret sharing or: how to cope
with perpetual leakage’, in Don Coppersmith (Ed.): Advances in Cryptology – Crypto ’95, August, Santa
Barbara, CA, pp.339–352.
[7] Bai, L. and Zou, X. (2009), Proactive Secret Sharing Scheme in matrix projection method, Int. J. Security
and Networks, Vol. 4, No. 4, pp.201–209.
[8] Lie Bai ,“A Reliable (k, n) Image Secret Sharing Scheme”, 2006
[9] Yike Yu “A Proactive Secret Sharing Scheme Based on Elliptic Curve Cryptography”, Education
Technology and Computer Science, 2009. ETCS '09.
[10] Ling Ma, Inst. of Inf. Security &amp; Secure Broadcasting &amp; Telev., Commun. Univ. of China, Beijing, China
Shouxun Liu ; Yongbin Wang ” A DRM model based on proactive secret sharing scheme for P2P
networks” Cognitive Informatics (ICCI), 2010 9th IEEE International Conference
[11] Zhengjun Cao, Olivier Markowitch, “Two Optimum Secret Sharing Schemes Revisited”, International
Seminar on Future Information Technology and Management Engineering, 2008 IEEE, p. 157-160.
[12] C.-C. Thien and J.-C. Lin, “Secret image sharing,” Computers &amp; Graphics, vol. 26, no. 5, pp. 765–770,
2002.

AUTHORS BIOGRAPHY
Sonali Patil pursuing Ph.D. from Amravati University. Her research interests include secret
sharing, data security. She has published several papers. Currently she is working as an
Assistant Professor at Computer Enginering Department in PCCOE, Akurdi, Pune.

Nikita Rana has completed Diploma in Computer Engg from MSBTE. Currently pursuing
Bachelors of Computer Engineering from Pune University

Prajol Hodge currently pursuing Bachelors of Computer Engineering from Pune University

Dhara Patel has completed Diploma in Information Technology from MSBTE. Currently
pursuing Bachelors of Computer Engineering fromPune University.

994

Vol. 6, Issue 2, pp. 987-994


Related documents


48i14 ijaet0514343 v6 iss2 987to994
36i14 ijaet0514336 v6 iss2 883to887
22i15 ijaet0715616 v6 iss3 1211to1219
ijetr2285
ijetr2217
pid4631333


Related keywords