Advanced
A (k,t,n) verifiable multi-secret sharing scheme based on adversary structure
A (k,t,n) verifiable multi-secret sharing scheme based on adversary structure
KSII Transactions on Internet and Information Systems (TIIS). 2014. Dec, 8(12): 4552-4567
Copyright © 2014, Korean Society For Internet Information
  • Received : March 09, 2014
  • Accepted : October 23, 2014
  • Published : December 31, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Jing Li
Licheng Wang
Jianhua Yan
Xinxin Niu
Yixian Yang

Abstract
A ( n , t , n ) secret sharing scheme is to share a secret among n group members, where each member also plays a role of a dealer,and any t shares can be used to recover the secret. In this paper, we propose a strong ( k , t , n ) verifiable multi-secret sharing scheme, where any k out of n participants operate as dealers. The scheme realizes both threshold structure and adversary structure simultaneously, and removes a trusted third party. The secret reconstruction phase is performed using an additive homomorphism for decreasing the storage cost. Meanwhile, the scheme achieves the pre-verification property in the sense that any participant doesn’t need to reveal any information about real master shares in the verification phase. We compare our proposal with the previous ( n , t , n ) secret sharing schemes from the perspectives of what kinds of access structures they achieve, what kinds of functionalities they support and whether heavy storage cost for secret share is required. Then it shows that our scheme takes the following advantages: (a) realizing the adversary structure, (b) allowing any k out of n participants to operate as dealers, (c) small sized secret share. Moreover, our proposed scheme is a favorable candidate to be used in many applications, such as secure multi-party computation and privacy preserving data mining, etc.
Keywords
1. Introduction
A secret sharing scheme (SSS) is to share a secret among a group of participants.In such a scheme, any qualified subset of participants, pooling together their shares, can recover the secret; whereas any unqualified subset could not obtain any information about it. Secret sharing schemes [8 , 12 , 19 - 20] have been widely used in practical applications, such as image preserving, implicit data security and e-voting, etc. Secret sharing schemes first introduced by Shamir [24] and Blakley [4] in 1979 were based on Lagrange polynomial interpolation and projective geometry theory, respectively. In threshold schemes, the shared secret can be reconstructed by any t or more than t participants, but any set having less than t participants cannot recover it.
During the past three decades, many threshold SSSs for a variety of features have been presented. In 1999, Lin et. al [16] designed a verifiable threshold multi-secret sharing scheme, based on the intractability of the factorization and the discrete logarithm module a large composite problems. The scheme provides efficient solutions against cheating by the dealer or any participant. In 2000, a multi-secret scheme [5] based on the systematic block codes was proposed. After that, a new multi-secret sharing scheme [27] based on Shamir’s secret sharing was constructed in 2004. Compared with the scheme reported in [5] , the new proposal in [27] has fewer public parameters and small storage. In 2008, a dynamic threshold multi-secret sharing scheme was given [25] , where many secrets are shared in such a way that all secrets can be reconstructed independently without refreshing the shares. Before 2009, while keeping a view on rounds in a SSS, the best known unconditionally secure protocol needs three rounds in sharing phase. Later, Patra et al. [21] , by introducing the definition of verification secret sharing with only negligible probability of error, designed a novel protocol that takes only two rounds in sharing phase and two rounds in reconstruction phase. Subsequently, a verification secret sharing scheme [1] within a total of three rounds (only two rounds in sharing and one round in reconstruction) was constructed. In 2014, the first multilevel threshold secret sharing based on Chinese Remainder Theorem was proposed in [10] , where each participant keepsonly one private share and the scheme is unconditionally secure. In such a scheme, shareholders are classified into different security subsets. The threshold value of a higher-level subset is smaller than the threshold value of a lower-level subset. However, the aforementioned threshold SSSs need a trusted third party for acting as a dealer.
In 1990, Ingemarsson and Simmons [13] introduced an idea for removing a trusted third party (TTP) in secret sharing, and then presented a simple protocol, where n participants generate shares of the scheme. Subsequently, Pedersen (1991) proposed the first ( t , n ) threshold secret sharing scheme [22] based on Shamir’s SSS. In Pedersen’s SSS, each participant also plays a role as a dealer for distributing secret shares to others without the assistance of TTPs. Meanwhile, each one randomly chooses an element, called sub-secret, and then distributes it using Shamir’s share generation algorithm to generate the sub-shares for other participants. By the property of additive homomorphism [2] of the reconstruction algorithm, each participant is able to combine all of his sub-shares into a single share, called master secret, which can be recovered with the knowledge of any t or more than t master shares using Lagrange polynomial interpolation. After that, some cryptosystem protocols [15 , 26] without trusted third parties were proposed. For example, the scheme reported in [26] is a threshold undeniable signature scheme without TTPs. The scheme in [15] shares a quantum secret without TTPs.
In 2010, Harn and Lin [11] presented a strong ( n , t , n ) verifiable secret sharing scheme (VSSS). Such type of schemes are called ( n , t , n ) SSS since the first parameter n refers to the number of dealers, the second parameter t refers to the threshold, and the third parameter n refers to the number of participants. Meanwhile, a new concept of strong t -consistency of shares has been introduced by Harn and Lin [11] . In the proposed scheme, it can be verified that all the qualified subsets can recover the same secret. After that, to decrease the number of verification polynomials for improving the efficiency of the scheme, Liu (2012) designed an efficient ( n , t , n ) VSSS [17] , in which participants generate only one verification polynomial for testing the strong t -consistency of shares. Then, Liu’s VSSS achieves multi-secret sharing.
In terms of access structures [3 , 9 , 14] , it can be seen that the access structure of ( t , n ) threshold SSSs is a special case of general access structures. In 2009, Qin [23] presented a secret sharing scheme that can achieve both the threshold and the adversary structure. However, each participant needs to keep a share of relatively big size m | S |, where m is the number of adversary sets and | S | is the size of the shared secret. In order to improve the efficiency, Zhao [28] proposed a new scheme with a share of size
PPT Slide
Lager Image
, where | a | is the size of populated data. In such schemes [23 , 28] , t or more than t participants are able to recover the shared secret in general, meanwhile some subsets of parties that each containing at least t participants cannot reconstruct the shared secret. Thus, the scheme can efficiently restrict the powers of participants. Finally, inspiring from the ideas proposed in [17 , 28] , our motivation is to design an improved SSS that can support adversary structure and remove the involvement of trusted third parties simultaneously.
Contributions. This paper presents a strong ( k , t , n ) verifiable multi-secret sharing scheme that removes a mutually trusted third party. Here, the first parameter k refers to the number of dealers, the second parameter t refers to the threshold value, and the third parameter n refers to the number of participants. That is, k out of n participants also act as dealers. Meanwhile, the scheme achieves two structures simultaneously: the threshold structure and the adversary structure. The former means that t or more than t participants can retrieve the master secret, and the latter one means that there are some subsets containing at least t participants cannot recover the secret. In addition, the scheme uses the property of additive homomorphism in the reconstruction phase for reducing the storage cost. Therefore, the size of share kept by each participant is bounded by
PPT Slide
Lager Image
.
Our scheme satisfies confidentiality in the sense that any unauthorized subset of participants cannot recover the shared secret. It can be shown that all sub-shares of the scheme are strong t -consistent, thus the proposed scheme can prevent any malicious participants from cheating. In particular, most VSSSs [6 - 7 , 28] only support post-verification property that each participant submits his secret share for doing reciprocal verifications. Therefore, the colluded participants (CPs) can obtain real shares of other participants but provide false shares for cheating others. Then, an unauthorized subset of CPs may recover the secret. Our scheme achieves pre-verification property, where all participants only need to publish their verification shares in the verification process, without revealing any information about the real master shares. Thus, the new proposal can prevent the attack from CPs. Finally, we compare our proposal with the previous ( n , t , n )SSSs [11 , 17 , 22] from the perspectives of what kinds of access structures they achieve, what kinds of functionalities they support and whether heavy storage cost for secret share is required. Then it shows that our scheme takes the following advantages: (a) achieving the adversary structure, (b) allowing any k out of n participants to operate as dealers, (c) small sized secret share.
The rest of this work is arranged as follows: In Section 2, some basic concepts are reviewed. Our scheme is presented in Section 3. Section 4 proves the confidentiality, verification and reconstruction properties of the newly proposed schemes. Finally, conclusions are provided in Section 5.
2. Preliminaries
In this section, we review some basic concepts.
- 2.1 Strong VSSS
Definition 1 . Strong t -consistent [11] . In a ( t , n ) secret sharing scheme, the n shares are strong t -consistent if (a) any subset containing t or more than t participants can determine the same secret; (b) any t −1 shares cannot determine the same secret.
Definition 2 . Strong VSSS [11] . In a strong verifiable secret sharing scheme, each participant can verify that the shares used for recovering the secret are strong t -consistent.
- 2.2 The access structure and the adversary structure
Let Q ={ P 1 , P 2 ,…, Pn } be the set of participants. An access structure [24] , denoted by Γ, is a collection of subsets of Q satisfying the monotone ascending property: for any A ′∈Γ and A ∈2 Q , A A ′ implies A ∈Γ. An adversary structure [24] , named as Ω, is a collection of subsets of Q satisfying the monotone descending property: for any A ′∈Ω and A ∈2 Q , A A ′ implies A ∈Ω. Because of the monotone properties, for any access structure Γ and any adversary structure Ω, it is enough to consider the minimum access structure:
PPT Slide
Lager Image
and the maximum adversary structure:
PPT Slide
Lager Image
3. Our scheme
In this section, we propose a strong ( k , t , n ) verifiable multi-secret sharing scheme that achieves both the threshold and the adversary structure.
- 3.1 The initialization phase
Let Q ={ P 1 , P 2 ,…, Pn } denote the set of n participants, and S denote the master secret. Let Q 0 ={ P 1 , P 2 ,…, Pk } be the set of k dealers ( k n and Q 0 Q ). Suppose that A 1 , A 2 ,…, Am are m subsets contained in Ω max and each of them has at least t participants. Now, we can define the access structure of our scheme as follows:
PPT Slide
Lager Image
That are, (a) if | X |≥ t and
PPT Slide
Lager Image
(j=1,2,⋯,m), then participants in set X can reconstruct the master secret S ; (b) if | X |< t or
PPT Slide
Lager Image
(1≤ j m ), then the participants in X cannot reconstruct S .
- 3.2 Distribution and Reconstruction of secrets
Let Fp be a finite field, where p is a large prime. Based on the previous ( n , t , n ) schemes [17] , the new scheme presents a more general model that any k out of n participants also operate as dealers without the assistance of a mutually trusted third party. The master secrets are the summations of threshold parameters and adversary control parameters. Then, each step of the construction is accomplished by two parallel algorithms for the threshold and the adversary structure: the threshold structure algorithm is based on Shamir’s secret sharing algorithm to create m master shares, and the adversary structure algorithm is used to generate control shares. Now, the distribution and reconstruction phases are described as follows:
Step 1. Master secret generation
Each participant Pα (1≤ α k ) constructs a polynomial
fa ( x )= S α,0 + S α,1 x +⋯+ S α,t−1 x t−1 ,
where S α,l ( S α,l
PPT Slide
Lager Image
, 0≤ l t −1) is an m -dimensional column vector. The master polynomial with respect to the threshold structure is defined by
PPT Slide
Lager Image
Let K =[ S 0 , S 1 ,⋯, S t−1 ] be an m × t matrix, where
PPT Slide
Lager Image
for l =0,1,⋯, t −1. On the other hand, Pα (1≤ α k ) selects an element Dα from Fp . The control parameter for the adversary structure is defined by
PPT Slide
Lager Image
Let M be an m × t matrix with all elements being D . Then the master secret S can be determined as
S = K + M .
Step 2. Sub-share generation
To the threshold structure, each participant Pα (1≤ α k ) uses Shamir’s distribution algorithm to generate sub-shares, s α,i = fα ( xi ) ( i =1,⋯, n ), for other participants. Here, s α,i is also an m -dimensional column vector. Then Pα sends s α,i to Pi secretly, and each participant Pi (1≤ i n ) will receive k sub-shares s α,i , for α =1,⋯, k .
In order to realize the adversary structure, each participant Pα creates an adversary control coalition Hα = { d α,1 , d α,2 ,⋯, d α,m } ( d α,j Fp , 1≤ α k and 1≤ j m ) such that
Dα = d α,1 + d α,2 +…+ d α,m .
If Pi Aj (1≤ j m ), then Pα deletes d α,j from Hα , and sends the remaining elements in Hα to Pi , for i =1,⋯, n . Each participant Pi (1≤ i n ) obtains k coalitions Hα ∖{ d α,j | Pi Aj , j =1,⋯, m } from participant Pα , for α =1,⋯, k .
Step 3. Master share generation
Each participant Pi computes one m -dimensional threshold share and mi adversary control shares. Pi calculates threshold master share
PPT Slide
Lager Image
Meanwhile, participant Pi combines the received sub-shares into the corresponding adversary control share as
PPT Slide
Lager Image
Then, he keeps a coalition
H (i) = { dj | Pi Aj , j =1,⋯, m }.
That is, | H (i) |= mi , and mi m .
Step 4. Verification phase
Using the method of verification in Liu SSS [11] , all participants perform together for selecting a k -tuple weight vector
PPT Slide
Lager Image
=( w 1 , w 2 ,…, wk ), such that
PPT Slide
Lager Image
is linearly independent to vector (1,1,⋯,1) , where wl Fp ( l =1,⋯, k ). Then, Pi (1≤ i n ) computes and broadcasts his verification share vi as
PPT Slide
Lager Image
Any t participants use Lagrange interpolation formula on the published verification shares. If the verification polynomial
PPT Slide
Lager Image
is t -1 exactly, then the master shares are strong t -consistent (Theorem 2 and Lemma 3). Actually, the verification property is pre-verifiable.
Step 5. Master secret reconstruction
For any authorized subset X ∈Γ (| X |≥ t ), the participants in X obtain dj ( j =1,2,…, m ) . With the help of the property of additive homomorphism, they compute
PPT Slide
Lager Image
for reconstructing the adversary control parameter. Meanwhile, with the knowledge of any t master shares with respect to the threshold structure, matrix S * can be recovered by Lagrange interpolation formula (denoted by FX (·)). That is, the master polynomial is
PPT Slide
Lager Image
where
PPT Slide
Lager Image
are threshold shares. Thus, the master secret matrix S as S = K + M can be reconstructed by the participants in X (see the correctness proof of Theorem 4).
Now, we analyze the aforementioned distribution and the reconstruction phases. Each participant Pi computes his adversary shares as
PPT Slide
Lager Image
, for j =1,⋯, m and Pi Aj , without storing all received sub-shares d α,j ( α =1,⋯, k , j =1,⋯, m ). Otherwise, the number of shares kept by each participant is proportional to the number of participants. Observe that the reconstruction of control parameter D is achieved based on the property of additive homomorphism. The following two tables present the distribution of master shares of the scheme.
Master share for threshold structure
PPT Slide
Lager Image
Master share for threshold structure
Master share for adversary structure
PPT Slide
Lager Image
Master share for adversary structure
4. Analysis and discussion
In the upcoming section, we present the analysis of our proposed scheme.
- 4.1 Security Proof
The security of secret sharing scheme is based on that of Shamir’s SSS, thus the proposal is secure in information theory. Now we prove that any unauthorized subset cannot recover the shared secret (Theorem 1).
Theorem 1. If | X |< t or X Aj (1≤ j m ) , then the participants in set X cannot reconstruct the master secret matrix S .
Proof. If | X |< t , the participants cannot get enough threshold shares to generate ( t −1) -degree master polynomial F ( x ). Furthermore, the vector
PPT Slide
Lager Image
=( w 1 , w 2 ,⋯, wk ) is linearly independent to (1,1,⋯,1), this implies that the verification shares cannot reveal any information about master shares. Thus, they cannot compute matrix K . On the other hand, if X Aj (1≤ j m ), any participant in X is not able to obtain the array { d 1,j , d 2,j ,⋯, d k,j }, then
PPT Slide
Lager Image
and thus, D cannot be computed. Therefore, the participants in X cannot recover the master secret matrix S .
- 4.2 The Verification property
The scheme satisfies the pre-verification property that any t participants can check the validity of secret shares without disclosing their real share. Now we give the verification analysis below.
Theorem 2. Any t or more than t participants can retrieve verification polynomial Fw ( x ).
Proof. With the knowledge of any t or more than t verification shares, the participants can recover verification polynomial
PPT Slide
Lager Image
with the help of the property of additive homomorphism and applying Lagrange interpolation formula on the verification shares. Let
PPT Slide
Lager Image
be an authorized subset of participants, and
PPT Slide
Lager Image
where
PPT Slide
Lager Image
( d =1,⋯, t ) are called interpolation coefficients. Then, we obtain the following equations:
PPT Slide
Lager Image
Thus, we have
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
We observe that Eq.(5) and Eq.(6) follow from Shamir’s secret reconstruction algorithm using Lagrange interpolation formula and the property of additive homomorphism, respectively.
Lemma 3. If the degree of verification polynomial
PPT Slide
Lager Image
is exactly t −1, then, the degree of master polynomial
PPT Slide
Lager Image
is exactly t −1.
Proof. We follow the same method for proving this lemma as used for proving Theorem 1 in [17] . Assume that there exists a polynomial fα ( x )(1≤ α k ), with degree larger than t −1 (say t ). Let aα be the first coordinate of the coefficient vector associated with the term xt of fα ( x ). Then, the probability that the degree of verification polynomial
PPT Slide
Lager Image
is t −1 exactly equals to the probability that w 1 a 1 + w 2 a 2 +…+ wkak =0. Since aα ( aα
PPT Slide
Lager Image
, 1≤ α k ) is selected randomly and independently, then this probability is
PPT Slide
Lager Image
, which can be ignored, for large prime p . Thus, if the degree of polynomial Fw ( x ) is exactly t −1, then the degree of each polynomial fα ( x ) (1≤ α k ) is at most t −1.
On the other hand, let
PPT Slide
Lager Image
be the first coordinate of the coefficient vector associated with the term x t−1 of fα ( x ). If at least one of
PPT Slide
Lager Image
(1≤ a k ) is nonzero, then the probability that
PPT Slide
Lager Image
is
PPT Slide
Lager Image
, which can also be negligible. Therefore, the degree of the master polynomial
PPT Slide
Lager Image
is exactly t −1.
From the aforementioned proof, we conclude that if colluded participants in Q 0 select polynomials fα ( x ) (1≤ α k ), having degree not equal to t −1, then they cannot pass the verification. Therefore, the proposed scheme satisfies the definition of strong VSSS. Meanwhile, since the vector ( w 1 ,⋯, wk ) is linearly independent to vector (1,⋯,1), hence no information about the real master shares can be revealed in the verification phase. Thus, the scheme has the advantage of pre-verification for that any participant doesn’t need to submit his real share in the verification phase. Moreover, it is worthwhile to note that the fraud probability of the new scheme is
PPT Slide
Lager Image
. This probability takes an exponential decline increment in the value of parameter m . Therefore, compared with the previous VSSS [17] having the fraud probability
PPT Slide
Lager Image
, our scheme just needs a smaller p for insuring that the corresponding fraud probability can be negligible. In such a way, the computational efficiency is improved to some extent.
- 4.3 The Reconstruction property
Theorem 4. For any authorized subset X ∈Γ, the participants in X can reconstruct the master secret S .
Proof. Let ( w 1 , w 2 ,⋯, wk )=(1,1,⋯,1) in the proof of Theorem 2, then we have that the participants in X can reconstruct master polynomial
PPT Slide
Lager Image
to obtain matrix K . On the other hand, since X ∈Γ, that is, | X |≥ t and
PPT Slide
Lager Image
( j =1,2,⋯, m ), this implies that there exists at least one participant having
PPT Slide
Lager Image
, for every j ∈{1,2,⋯, m }. Then the participants in X can obtain set { d 1 , d 2 ,⋯, dm } by pooling together their shares. Furthermore, we have that
PPT Slide
Lager Image
The second equation follows from the property of additive homomorphism. Thus, all the participants in X work together for computing
PPT Slide
Lager Image
and get matrix M . Hence, they can recover the master secret matrix S .
- 4.4 The Dynamic property
A secret sharing scheme is said to be dynamic, if any participant can join and leave dynamically. The previous ( n , t , n ) threshold SSSs [11 , 17] realize the dynamic property. Now we point out that our scheme under the complicated model also supports this property and analyze various cases in terms of control parameter D for the adversary structure.
Case 1. Suppose that participant Pl leaves from set { P 1 ,…, Pn }. If Pl Q 0 , then control parameter D of the scheme is determined as
PPT Slide
Lager Image
Participant Pi (1≤ i n , i l ) just needs to delete set H 1 ∖{ d l,j | Pi Aj , j =1,⋯ m } received from Pl . The remaining participants compute their new shares as
PPT Slide
Lager Image
If Pi Q Q 0 , then k dealers need to update their control parameters d α,j , for α =1,⋯, k , and Pi Aj . The participants compute their new shares as
PPT Slide
Lager Image
Case 2. Suppose that a new participant P n+1 joins. If P n+1 contained in Q 0 acts as a dealer, then, he is required to choose one element D n+1 (∈ Fp ) and generate a control coalition H n+1 = { d n+1,1 , d n+1,2 ,⋯, d n+1,m } such that
PPT Slide
Lager Image
. Then, the control parameter D is determined as
PPT Slide
Lager Image
P n+1 sends H n+1 ∖ { d n+1,j | Pi Aj , j =1,⋯, m } to participant Pi (1≤ i n ). Similarly, participant Pα (1≤ α k ) needs to send Hα ∖ { d α,j | P n+1 Aj , j =1,⋯, m } to P n+1 . All participants compute their new shares as
PPT Slide
Lager Image
If P n+1 Q 0 , then he receives Hα ∖ { d α,j | P n+1 Aj , j =1,⋯, m } from Pα (1≤ α k ) and computes
PPT Slide
Lager Image
.
The analysis on threshold parameter K can be discussed in the same way.
- 4.5 Efficiency analysis
In this section, we analyze the efficiency of the newly proposed scheme from angles of computational complexity and communication cost, respectively.
With respect to the computation complexity, we mainly count the number of polynomial evaluation and polynomial interpolation in three stages:
• Sharing phase: Each participant Pα (1≤ α k ) computes s α,i = fα ( xi ) ( i =1,⋯, n ) and sends s α,i to Pi , where s α,i is an m -dimensional column vector. Thus, mnk polynomial evaluations are needed.
• Verification phase: Each participant Pi (1≤ i n ) computes an m -dimensional verification share
PPT Slide
Lager Image
. The operation of the form of
PPT Slide
Lager Image
can be viewed as a polynomial evaluation. Thus, mn polynomial interpolations should be used. Besides, t participants adopt Lagrange polynomial interpolation on the published verification shares. Thus, m polynomial interpolations are needed.
• Reconstruction phase: Based on Lagrange interpolation formula, the secret verification and reconstruction can be completed by computing the same interpolating coefficients yld ( d =1,⋯, t ). Thus, the reconstruction phase only needs m polynomial evaluations.
Computational complexity
PPT Slide
Lager Image
Computational complexity
Remark. The above analysis on computational complexity is aimed at the threshold structure. In addition, since the realization of the adversary structure only utilizes simple module additions, therefore, the operation of this part can be negligible.
With respect to the communication cost, we describe the bits of communication cost for the threshold and the adversary structure:
• Access structure: Pα (1≤ α k ) sends m -dimensional column vector s α,i to Pi (1≤ i n ). Thus, this part of communication costs mnk ⋅log p bits.
• Adversary structure: Each participant Pα (1≤ α k ) sends Hα ∖ { d α,j | P n+1 Aj , j =1,⋯, m } to Pi (1≤ i n ). Since ∣ Hα ∖ { d α,j | P n+1 Aj , j =1,⋯, m }∣≤ m , then this part of communication cost is bounded by mnk ⋅log p bits.
Communication cost
PPT Slide
Lager Image
Communication cost
- 4.6 Information rate
The information rate [18] of one secret sharing scheme is defined by
PPT Slide
Lager Image
where | S | denotes the size of secret, and | S ( Pi )| is the size of share kept by participant Pi .
In the scheme, we have that
PPT Slide
Lager Image
Since t ≥2 and m > max ( mi ), then ρ >
PPT Slide
Lager Image
and ρ >1. Meanwhile, we can obverse that the size of share kept by each participant is bounded by
PPT Slide
Lager Image
. In Zhao’s scheme, the size of share is
PPT Slide
Lager Image
[28] . For convenience, let | a |, the size of populated data, be zero, then the corresponding information rate is given by
PPT Slide
Lager Image
. The two schemes have equal information rates, that is,
PPT Slide
Lager Image
, then m = t +1. Then, we have that Zhao’s SSS has a higher information rate if m t ; our scheme is superior to Zhao’s SSS if m t +1. Considering the computational complexity of Lagrange interpolation in a threshold SSS, the designer normally selects a small integer as the threshold value. That is, in the most cases, m t +1 holds and our scheme has higher information rate than Zhao’s SSS.
Finally, the performance comparison among SSSs of [17 , 28] and our proposal is demonstrated as follows:
The comparisons given in Table 5 can be further depicted in Fig. 1 and Fig. 2 . In Fig. 1 we compare our proposal with the schemes given in [28] and [17] from the perspectives of what kinds of functionalities they support, which kind of security they achieve, and whether the trusted third party and some complex computation (such as modular exponential) are required. From Figure 1 , we can see that our proposal covers all these six desirable merits: Simultaneously supporting adversary structure, threshold structure and pre-verification, achieving information-theory security (or equivalently, without depend upon any intractability assumption), and needless TTP and modular exponential computation. In Figure 2 we compare these schemes from the perspective of information rate. It shows that our scheme can gain even higher information rate. In particular, with the increase of m (i.e., the number of adversary sets) or t (i.e., the threshold value), the advantages of our proposal become even clear.
Performance comparison
PPT Slide
Lager Image
Performance comparison
PPT Slide
Lager Image
Functionalities comparison
PPT Slide
Lager Image
Information rate comparison
Remark. Our scheme has relatively higher computational complexity and communication cost among the three schemes, since it achieves more properties than scheme [17] and scheme [28] , respectively.
5. Conclusions
In this paper, based on the previous ( n , t , n ) VSSSs, we propose a more general ( k , t , n ) VSSS, in which any k out of n participants also operate as dealers. The scheme realizes the threshold and the adversary structure simultaneously. In such a way, it restricts the powers of participants in secret reconstruction phase efficiently. Taking the advantage of additive homomorphism, the size of share stored by each participant is reduced for improving the efficiency of our scheme. In addition, our scheme has the advantage of the pre-verification property.
BIO
Jing Li received the B.S. degree from Inner Mongol Normal University in 2010 and the M.S. degree from Shananxi Normal University in 2013. Her current research interests include modern cryptography, network security, finite field and its applications, etc. She is a doctoral candidate studying in Beijing University of Posts and Telecommunications.
Licheng Wang received the B.S. degree from Northwest Normal University in 1995, the M.S. degree from Nanjing University in 2001, and the PhD degree from Shanghai Jiao Tong University in 2007. His current research interests include modern cryptography, network security, trust management, etc. He is an associate professor in Beijing University of Posts and Telecommunications.
Jianhua Yan received the B.S. degree B.S. degree from JiLin University in 2002, the M.S. degree from LiaoNing University of Petro-Chemical Technology in 2005. His current research interests include lattice-based cryptosystem and information security. Now he is a doctoral candidate studying in Beijing University of Posts and Telecommunications.
Xinxin Niu is an professor of Computer Science and Technology at Beijing University of Posts and Telecommunications. She received the MS degree from Beijing University of Posts and Telecommunications in 1988, the PhD degree from Chinese University of Hong Kong in 1997. Her current research interests include network security, digital watermarking and digital rights management, etc.
Yixian Yang is a Professor of Computer Science and Technology at Beijing University of Posts and Telecommunications and also the director of the National Engineering Laboratory for Disaster Backup and Recovery of China. He is a fellow of China Institute of Communications (CIC), and a council member of Chinese Institute of Electronics (CIE) and Chinese Association for Cryptologic Research (CACR). He is the editor in chief of Journal on Communications of China. He received his MS degree in Applied Mathematics and PhD degree in Signal and Information Processing from Beijing University of Posts and Telecommunications in 1986 and 1988, respectively. His research interests include coding theory and cryptography, information security and network security, disaster backup and recovery, signal and information processing, etc.
References
Agrawal S. 2012 “Verifiable secret sharing in a total of three rounds,” Information Processing Letters 112 856 - 859    DOI : 10.1016/j.ipl.2012.08.003
Benaloh J.C. 1986 “Secret sharing homomorphisms: keeping shares of a secret. CRYPTO,” Lecture Notes in Computer Science Springer 263 251 - 260
Benaloh J.C. , Leichter J. 1990 “Generalized Secret Sharing and Monotone Functions,”CRYPTO’88 Lecture Notes in Computer Science Springer 403 27 - 35
Blakley G.R. “Safeguarding cryptographic keys,” in Proc. of AFIPS 1979 National Computer Conference June, 1979 313 - 317
Chien H. Y. , Jan J.K. , Tseng Y.M. “A practical (t,n) multi-secret sharing scheme,” IEICE Transactions on Communications/Electronics/Information and Systems 2000 2762 - 2765
Dehkordi M.H. , Mashhadi S. 2008 “An efficient threshold verifiable multi-secret sharing,” Computer Standards & Interfaces 30 187 - 190    DOI : 10.1016/j.csi.2007.08.004
Dehkordi M.H. , Mashhadi S. 2008 “New efficient and practical verifiable multi-secret sharing schemes,” Information Sciences 178 2262 - 2274    DOI : 10.1016/j.ins.2007.11.031
Guo C. , Chang C.C. , Qin C. 2012 “A hierarchical threshold secret image sharing,” Pattern Recognition Letters 33 83 - 91    DOI : 10.1016/j.patrec.2011.09.030
Guo Y.B. , Ma J.F. 2004 “Practical secret sharing scheme realizing generalized adversary structure,” Journal of Computer Science and Technology 19 564 - 569    DOI : 10.1007/BF02944759
Harn L. , Fuyou M. 2014 “Multilevel threshold secret sharing based on the Chinese Remainder Theorem,” Information Processing Letters 114 504 - 509    DOI : 10.1016/j.ipl.2014.04.006
Harn L. , Lin C. 2010 “Strong (n,t,n) verifiable secret sharing scheme,” Information Sciences 180 3059 - 3064    DOI : 10.1016/j.ins.2010.04.016
Iftene S. 2007 “General Secret Sharing Based on the Chinese Remainder Theorem with Applications in E-Voting,” Electronic Notes in Theoretical Computer Science 186 67 - 84    DOI : 10.1016/j.entcs.2007.01.065
Ingemarsson Simmons “A Protocol to Set Up Shared Secret Schemes without the Assistance of a Mutually Trusted Party,” Advances in Cryptology: Proceedings of EUROCRYPT 1990
Ito M. , Saito A. , Nishizeki T. “Secret sharing scheme realizing general access structure,” in Proc. of IEEE Global Telecommunications Conference-GLOBECOM’87 1987 99 - 102
Li Q. , Long D.Y. , Chan W.H. , Qiu D.W. “Sharing a quantum secret without a trusted party,” URL
Lin T.Y. , Wu T.C. 1999 “(t, n) threshold verifiable multisecret sharing scheme based on factorisation intractability and discrete logarithm module a composite problems,” IEE Proceedings on Computers and Digital Techniques 146 264 - 268    DOI : 10.1049/ip-cdt:19990708
Liu Y.X. , Harn L. , Yang C.N. , Zhang Y.Q. 2012 “Efficient (n,t,n) secret sharing schemes,” Journal of Systems and Software 85 1325 - 1332    DOI : 10.1016/j.jss.2012.01.027
Padro C. , Saez G. 2002 “Lower bounds on the information rate of secret sharing schemes with homogeneous access structure,” Information Processing Letters 83 345 - 351    DOI : 10.1016/S0020-0190(02)00213-2
Pakniat N. , Noroozi M. , Eslami Z. 2014 “Secret image sharing scheme with hierarchical threshold access structure,” Journal of Visual Communication and Image Representation 25 1093 - 1101    DOI : 10.1016/j.jvcir.2014.03.004
Parakh A. , Kak S. 2011 “Space efficient secret sharing for implicit data security,” Information Sciences 181 335 - 341    DOI : 10.1016/j.ins.2010.09.013
Patra A. , Choudhary A. , Rabin T. , Rangan C.P. 2009 “The Round Complexity of Verifiable Secret Sharing Revisited. CRYPTO,” Lecture Notes in Computer Science Springer 5677 487 - 504
Pedersen T.P. 1991 “A threshold cryptosystem without a trusted party,”in Proc. of the Eurocrypt’91 Lecture Notes in Computer Science Springer 547 522 - 526
Qin H.W. , Dai Y.W. , Wang Z.Q. 2009 “A secret sharing scheme based on (t,n) threshold and adversary structure,” International Journal of Information Security 8 379 - 385    DOI : 10.1007/s10207-009-0085-2
Shamir A. 1979 “How to share a secret,” Communications of the ACM 22 612 - 613    DOI : 10.1145/359168.359176
Shi R.H. , Huang L.S. , Hong Z. “An Efficient (t, n)-Threshold Multi-Secret Sharing Scheme,” in Proc. of International Conference on Networks & Soft Computing 2008 580 - 583
Wang G.L. , Qing S. 2002 "A Threshold Undeniable Signature Scheme without a Trusted Party,” Journal of Software 13 1757 - 1764
Yang C.C. , Chang T.Y. , Hwang M.S. 2004 “A (t,n) multi-secret sharing scheme,” Applied Mathematics and Computation 151 483 - 490    DOI : 10.1016/S0096-3003(03)00355-2
Zhao D.W. , Peng H.P. , Wang C. , Yang Y.X. 2012 “A secret sharing scheme with a short share realizing the (t,n) threshold and the adversary structure,” Computers and Mathematics with Applications 64 611 - 615    DOI : 10.1016/j.camwa.2011.12.067