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 multisecret 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 preverification 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 multiparty computation and privacy preserving data mining, etc.
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 evoting, 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 multisecret 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 multisecret scheme
[5]
based on the systematic block codes was proposed. After that, a new multisecret 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 multisecret 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 higherlevel subset is smaller than the threshold value of a lowerlevel 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 subsecret, and then distributes it using Shamir’s share generation algorithm to generate the subshares for other participants. By the property of additive homomorphism
[2]
of the reconstruction algorithm, each participant is able to combine all of his subshares 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 multisecret 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
, 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 multisecret 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
.
Our scheme satisfies confidentiality in the sense that any unauthorized subset of participants cannot recover the shared secret. It can be shown that all subshares 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 postverification 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 preverification 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}
,…,
P_{n}
} 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:
and the maximum adversary structure:
3. Our scheme
In this section, we propose a strong (
k
,
t
,
n
) verifiable multisecret sharing scheme that achieves both the threshold and the adversary structure.
 3.1 The initialization phase
Let
Q
={
P
_{1}
,
P
_{2}
,…,
P_{n}
} denote the set of
n
participants, and
S
denote the master secret. Let
Q
_{0}
={
P
_{1}
,
P
_{2}
,…,
P_{k}
} be the set of
k
dealers (
k
≤
n
and
Q
_{0}
⊆
Q
). Suppose that
A
_{1}
,
A
_{2}
,…,
A_{m}
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:
That are, (a) if 
X
≥
t
and
(j=1,2,⋯,m), then participants in set
X
can reconstruct the master secret
S
; (b) if 
X
<
t
or
(1≤
j
≤
m
), then the participants in
X
cannot reconstruct
S
.
 3.2 Distribution and Reconstruction of secrets
Let
F_{p}
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
f_{a}
(
x
)=
S
_{α,0}
+
S
_{α,1}
x
+⋯+
S
_{α,t−1}
x
^{t−1}
,
where
S
_{α,l}
(
S
_{α,l}
∈
, 0≤
l
≤
t
−1) is an
m
dimensional column vector. The master polynomial with respect to the threshold structure is defined by
Let
K
=[
S
_{0}
,
S
_{1}
,⋯,
S
_{t−1}
] be an
m
×
t
matrix, where
for
l
=0,1,⋯,
t
−1. On the other hand,
P_{α}
(1≤
α
≤
k
) selects an element
D_{α}
from
F_{p}
. The control parameter for the adversary structure is defined by
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. Subshare generation
To the threshold structure, each participant
P_{α}
(1≤
α
≤
k
) uses Shamir’s distribution algorithm to generate subshares,
s
_{α,i}
=
f_{α}
(
x_{i}
) (
i
=1,⋯,
n
), for other participants. Here,
s
_{α,i}
is also an
m
dimensional column vector. Then
P_{α}
sends
s
_{α,i}
to
P_{i}
secretly, and each participant
P_{i}
(1≤
i
≤
n
) will receive
k
subshares
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}
∈
F_{p}
, 1≤
α
≤
k
and 1≤
j
≤
m
) such that
D_{α}
=
d
_{α,1}
+
d
_{α,2}
+…+
d
_{α,m}
.
If
P_{i}
∈
A_{j}
(1≤
j
≤
m
), then
P_{α}
deletes
d
_{α,j}
from
H_{α}
, and sends the remaining elements in
H_{α}
to
P_{i}
, for
i
=1,⋯,
n
. Each participant
P_{i}
(1≤
i
≤
n
) obtains
k
coalitions
H_{α}
∖{
d
_{α,j}

P_{i}
∈
A_{j}
,
j
=1,⋯,
m
} from participant
P_{α}
, for
α
=1,⋯,
k
.
Step 3. Master share generation
Each participant
P_{i}
computes one
m
dimensional threshold share and
m_{i}
adversary control shares.
P_{i}
calculates threshold master share
Meanwhile, participant
P_{i}
combines the received subshares into the corresponding adversary control share as
Then, he keeps a coalition
H
^{(i)}
= {
d_{j}

P_{i}
∉
A_{j}
,
j
=1,⋯,
m
}.
That is, 
H
^{(i)}
=
m_{i}
, and
m_{i}
≤
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
=(
w
_{1}
,
w
_{2}
,…,
w_{k}
), such that
is linearly independent to vector (1,1,⋯,1) , where
w_{l}
∈
F_{p}
(
l
=1,⋯,
k
). Then,
P_{i}
(1≤
i
≤
n
) computes and broadcasts his verification share
v_{i}
as
Any
t
participants use Lagrange interpolation formula on the published verification shares. If the verification polynomial
is
t
1 exactly, then the master shares are strong
t
consistent (Theorem 2 and Lemma 3). Actually, the verification property is preverifiable.
Step 5. Master secret reconstruction
For any authorized subset
X
∈Γ (
X
≥
t
), the participants in
X
obtain
d_{j}
(
j
=1,2,…,
m
) . With the help of the property of additive homomorphism, they compute
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
F_{X}
(·)). That is, the master polynomial is
where
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
P_{i}
computes his adversary shares as
, for
j
=1,⋯,
m
and
P_{i}
∉
A_{j}
, without storing all received subshares
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
Master share for threshold structure
Master share for adversary structure
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
⊆
A_{j}
(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
=(
w
_{1}
,
w
_{2}
,⋯,
w_{k}
) 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
⊆
A_{j}
(1≤
j
≤
m
), any participant in
X
is not able to obtain the array {
d
_{1,j}
,
d
_{2,j}
,⋯,
d
_{k,j}
}, then
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 preverification 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
F_{w}
(
x
).
Proof.
With the knowledge of any
t
or more than
t
verification shares, the participants can recover verification polynomial
with the help of the property of additive homomorphism and applying Lagrange interpolation formula on the verification shares. Let
be an authorized subset of participants, and
where
(
d
=1,⋯,
t
) are called interpolation coefficients. Then, we obtain the following equations:
Thus, we have
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
is exactly
t
−1, then, the degree of master polynomial
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
x^{t}
of
f_{α}
(
x
). Then, the probability that the degree of verification polynomial
is
t
−1 exactly equals to the probability that
w
_{1}
a
_{1}
+
w
_{2}
a
_{2}
+…+
w_{k}a_{k}
=0. Since
a_{α}
(
a_{α}
∈
, 1≤
α
≤
k
) is selected randomly and independently, then this probability is
, which can be ignored, for large prime
p
. Thus, if the degree of polynomial
F_{w}
(
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
be the first coordinate of the coefficient vector associated with the term
x
^{t−1}
of
f_{α}
(
x
). If at least one of
(1≤
a
≤
k
) is nonzero, then the probability that
is
, which can also be negligible. Therefore, the degree of the master polynomial
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}
,⋯,
w_{k}
) 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 preverification 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
. This probability takes an exponential decline increment in the value of parameter
m
. Therefore, compared with the previous VSSS
[17]
having the fraud probability
, 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}
,⋯,
w_{k}
)=(1,1,⋯,1) in the proof of Theorem 2, then we have that the participants in
X
can reconstruct master polynomial
to obtain matrix
K
. On the other hand, since
X
∈Γ, that is, 
X
≥
t
and
(
j
=1,2,⋯,
m
), this implies that there exists at least one participant having
, for every
j
∈{1,2,⋯,
m
}. Then the participants in
X
can obtain set {
d
_{1}
,
d
_{2}
,⋯,
d_{m}
} by pooling together their shares. Furthermore, we have that
The second equation follows from the property of additive homomorphism. Thus, all the participants in
X
work together for computing
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
P_{l}
leaves from set {
P
_{1}
,…,
P_{n}
}. If
P_{l}
∈
Q
_{0}
, then control parameter
D
of the scheme is determined as
Participant
P_{i}
(1≤
i
≤
n
,
i
≠
l
) just needs to delete set
H
_{1}
∖{
d
_{l,j}

P_{i}
∈
A_{j}
,
j
=1,⋯
m
} received from
P_{l}
. The remaining participants compute their new shares as
If
P_{i}
∈
Q
∖
Q
_{0}
, then
k
dealers need to update their control parameters
d
_{α,j}
, for
α
=1,⋯,
k
, and
P_{i}
∉
A_{j}
. The participants compute their new shares as
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}
(∈
F_{p}
) and generate a control coalition
H
_{n+1}
= {
d
_{n+1,1}
,
d
_{n+1,2}
,⋯,
d
_{n+1,m}
} such that
. Then, the control parameter
D
is determined as
P
_{n+1}
sends
H
_{n+1}
∖ {
d
_{n+1,j}

P_{i}
∈
A_{j}
,
j
=1,⋯,
m
} to participant
P_{i}
(1≤
i
≤
n
). Similarly, participant
P_{α}
(1≤
α
≤
k
) needs to send
H_{α}
∖ {
d
_{α,j}

P
_{n+1}
∈
A_{j}
,
j
=1,⋯,
m
} to
P
_{n+1}
. All participants compute their new shares as
If
P
_{n+1}
∉
Q
_{0}
, then he receives
H_{α}
∖ {
d
_{α,j}

P
_{n+1}
∈
A_{j}
,
j
=1,⋯,
m
} from
P_{α}
(1≤
α
≤
k
) and computes
.
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_{α}
(
x_{i}
) (
i
=1,⋯,
n
) and sends
s
_{α,i}
to
P_{i}
, where
s
_{α,i}
is an
m
dimensional column vector. Thus,
mnk
polynomial evaluations are needed.
• Verification phase:
Each participant
P_{i}
(1≤
i
≤
n
) computes an
m
dimensional verification share
. The operation of the form of
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
y_{ld}
(
d
=1,⋯,
t
). Thus, the reconstruction phase only needs
m
polynomial evaluations.
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
P_{i}
(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}
∈
A_{j}
,
j
=1,⋯,
m
} to
P_{i}
(1≤
i
≤
n
). Since ∣
H_{α}
∖ {
d
_{α,j}

P
_{n+1}
∈
A_{j}
,
j
=1,⋯,
m
}∣≤
m
, then this part of communication cost is bounded by
mnk
⋅log
p
bits.
Communication cost
 4.6 Information rate
The information rate
[18]
of one secret sharing scheme is defined by
where 
S
 denotes the size of secret, and 
S
(
P_{i}
) is the size of share kept by participant
P_{i}
.
In the scheme, we have that
Since
t
≥2 and
m
>
max
(
m_{i}
), then
ρ
>
and
ρ
>1. Meanwhile, we can obverse that the size of share kept by each participant is bounded by
. In Zhao’s scheme, the size of share is
[28]
. For convenience, let 
a
, the size of populated data, be zero, then the corresponding information rate is given by
. The two schemes have equal information rates, that is,
, 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 preverification, achieving informationtheory 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
Functionalities comparison
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 preverification 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 PetroChemical Technology in 2005. His current research interests include latticebased 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.
View Fulltext
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) multisecret sharing scheme,”
IEICE Transactions on Communications/Electronics/Information and Systems
2000
2762 
2765
Dehkordi M.H.
,
Mashhadi S.
2008
“An efficient threshold verifiable multisecret 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 multisecret sharing schemes,”
Information Sciences
178
2262 
2274
DOI : 10.1016/j.ins.2007.11.031
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
Iftene S.
2007
“General Secret Sharing Based on the Chinese Remainder Theorem with Applications in EVoting,”
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 ConferenceGLOBECOM’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/ipcdt: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/S00200190(02)002132
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
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/s1020700900852
Shi R.H.
,
Huang L.S.
,
Hong Z.
“An Efficient (t, n)Threshold MultiSecret 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
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