A NEW ),( n
t
MULTI-SECRET SHARING SCHEME BASED ON
LINEAR ALGEBRA
Seyed Hamed Hassani
Department of Electrical Engineering
Department of Mathematical Science
Sharif University of Technology
P.O.Box 11365-9363, Tehran Iran
Mohammad Reza Aref
Department of Electrical Engineering
Sharif University of Technology
P.O.Box 11365-9363, Tehran Iran
Keywords: Threshold scheme, Secret Sharing, Multi-secret sharing, Linear algebra, Cryptography.
Abstract: In this paper, a new multi-secret threshold scheme based on linear algebra and matrices is proposed. Unlike
many recently proposed methods, this method lets the use of conventional cryptographic algorithms in shar-
ing multiple secrets. Our scheme is a multi-use scheme, which in some cases, the amount of computations is
considerably reduced. Also, in this paper bounds on the maximum number of participants, for a given
threshold value, are obtained.
1 INTRODUCTION
Secret sharing has been a subject of study for the
last three decades and is a useful tool in modern
cryptography. It plays an important role in protect-
ing information from getting lost, stolen, or de-
stroyed and has been more applicable in recent
years. Secret sharing schemes either can be identi-
fied as threshold schemes or generalized group-
oriented cryptosystems. Various approaches have
been proposed for the general problem. In 1979, the
first
),( nt threshold scheme was proposed by Blak-
ley (Blakley , 1979) and Shamir (Shamir, 1979)
independently, where, Blakley’s scheme is based on
linear projective geometry and Shamir’s scheme is
based on the Lagrange interpolating polynomial. In
a
),( nt threshold scheme, a secret can be shared
among n participants and at least
t
participants are
required to reconstruct the secret, while
)1(
−
t or
fewer participants can obtain no information about
the secret. In a multi-secret sharing scheme, there
are multiple secrets to be distributed during a secret
sharing process but only one share is kept by each
participant and many secrets can be shared without
refreshing the share .
As mentioned in (Jackson et al, 1994), multi-
secret sharing schemes may be classified into two
groups: One time-use and multi-time use schemes.
In a one time-use scheme, the secret holder redis-
tributes new shares to each participant once a par-
ticular secret is reconstructed. The schemes in
(Blakley , 1979), (Shamir, 1979) and (Karnin et al.,
1983) are of this type. On the other hand, in a multi-
time use scheme, the shadows owned by any partici-
pant remain still secret to others, after the recon-
struction of multiple secrets. Therefore, there is no
need to redistribute new shares to each participant,
which is a costly process in both time and resources
((Jackson et al, 1994)). The schemes in (Deng et al.,
1995) (Chien et al., 2000) (Bertilsson et al.,, 1992)
and (Pang, 2005) are of this type.
A special class of secret sharing schemes are
the linear threshold schemes which are based on
vector spaces and systematic linear block codes
((Deng et al., 1995) (Chien et al., 2000) (Bertilsson
443
Hamed Hassani S. and Reza Aref M. (2006).
A NEW (t , n) MULTI-SECRET SHARING SCHEME BASED ON LINEAR ALGEBRA.
In Proceedings of the International Conference on Security and Cryptography, pages 443-449
DOI: 10.5220/0002098704430449
Copyright
c
SciTePress
et al.,, 1992) (Karnin et al., 1983)).The proposed
scheme is a linear threshold scheme in which the
secret
S is stored in a matrix (or in a linear sub-
space). This matrix (or linear subspace) has the
property of being constructed by special (author-
ized) set of vectors and of course, a non-special
(non-authorized) set would give no information
about it. The scheme is applicable in both one-secret
and multi-secret sharing systems and is a multi-time
use scheme.
One major problem in many of the previously
proposed linear threshold schemes such as Deng, et
al. scheme (Deng et al., 1995) , Chien, et al.
scheme (Chien et al., 2000), is the dependency of
secret reconstruction process on the number of par-
ticipants (
n
). For example, in Chien’s scheme, in
order to reconstruct
p secrets, solving
tpn −+ simultaneous linear equations is required.
This dependency, especially when
n is a large
number with respect to
t
, would make the scheme
somehow inefficient. In the proposed scheme, the
secret decomposition scheme is totally independent
of the number of participants.
In most of the previous schemes the computa-
tions are performed in
)(
m
qGF where,
m
q is larger
than all the used numbers. In fact, all the used num-
bers are elements in this field. But in our scheme the
computations could be done in a field of any size,
hence, reducing the amount of computations.
The paper is organized as follows. In section
2, we shall briefly review Chien’s scheme as an
example of a recently proposed linear threshold
scheme. In section 3, we shall present the proposed
scheme and make some security analysis. In section
4, a comparison is given between our scheme and
other schemes such as Chien’s. Finally, in section 5,
conclusions are presented.
2 REVIEW OF CHIEN’S
SCHEME
Before presenting Chien’s scheme (Chien et al.,
2000), we give a definition of a one-way func-
tion
),( yxf with two variables
x
and y . One-way
function has been used in Chien’s scheme, and will
be used in our scheme.
Definition 1 If function
),( yxf denotes a
two-variable one-way function that maps any
x
and
y to a bit string ),( yxf of fixed length ((He et
al., 1995)), the function has the following properties:
a) Given
x
and y , it is easy to com-
pute
),( yxf .
b) Given
x
and ),( yxf , it is hard to com-
pute
y
.
c) Given
y and ),( yxf , it is hard to com-
pute
x
.
d) Having no knowledge of
y
it is hard to
compute
),( yxf for any
x
.
e) Given
y , it is hard to find two different
values
1
x and
2
x such that ),(),(
21
yxfyxf = .
f) Given pairs of
i
x and ),( yxf
i
, it is hard to
compute
),( yxf
′
for
i
xx
≠
′
.
The proof of existence, as well as few exam-
ples on construction of such one-way functions is
given in ((He et al., 1995)). Chien’s scheme is as
follows:
Step 1 Let
)2(
m
GF be a large finite field
such that all the used
numbers are its elements and let
g
be a primitive
element ; Let
))(2,( tpnpnG
−
++
denote a special type of
systematic block codes generator
matrix
[
P
]
tpnpn
I
−+×+ )(2)(
where
I
is an identity matrix of or-
der
)()( pnpn
+
×
+
and
P
is a )()( tpnpn
−
+×+
matrix
[
]
)1)(1( −− ji
g for
pni
+
=
~1 and
tpnj
−
+
=
~1 ((Lin, 2004) ); The secret
holder randomly selects
n
ss ,...,
1
as participants’ secret
shadows.
Step 2 The secret holder randomly se-
lects
r
and computes
),(
i
srf for each participant.
Step 3 Assuming
p
PPP ,...,,
21
are the p
secrets to be shared, let
)],(),...,,(),,(,,...,,[
2121 np
srfsrfsrfPPPD = be
the vector
of information symbols. The secret
holder computes the
corresponding code word
DGV
=
as follows:
SECRYPT 2006 - INTERNATIONAL CONFERENCE ON SECURITY AND CRYPTOGRAPHY
444
T
nptpn
srfsrfsrfPPPcccV )],(),...,,(),,(,,...,,,,...,,[
212121 −+
=
(1)
where:
∑∑
+
+=
−
−−
=
−−
+=
pn
pi
pi
ji
p
i
j
ji
j
srfgPgc
1
)1)(1(
1
)1)(1(
),(
(2)
Step 4 Publish
),...,,,(
21 tpn
cccr
−+
in an
authenticated manner.
The secret reconstruction process is very sim-
ple and straightforward. In order to reconstruct the
p secrets, at least
t
participants poll their pseudo
shadows
),(
i
srf . Thus, the )( tpn −+ equations in
(2) are obtained with only
)( tpn −+ unknown
symbols. Therefore, the
p secrets can be obtained
by solving the simultaneous
)( tpn −+ linear equa-
tions in (2). The important point is that the secret
shadows
i
s will not be revealed even though all of
the symbols
),(
i
srf are exposed to the partici-
pants. Therefore, redistribution of secret shadows
among the participants, after the secret-
reconstruction process, is not required. This is due to
the properties of the one-way two-variable func-
tion
),( srf . The secret holder only has to choose
and publish another random integer
r
. The number
of public values in Chien’s scheme is
)1(
+
−
+ tpn
according to Step 4.
3 THE PROPOSED SCHEME
3.1 Description of the Basic Idea
Suppose that V is a finite
m
-dimensional vector
space over a field
F
and
E
is a
t
- dimensional
subspace of
V . Obviously
E
is spanned by any
linearly independent set
},...,,{
21 t
A
α
α
α
= of its
vectors (
)( E
l
∈
α
for tl ~1= ). The idea is first to
find a special and unique set of linearly inde-
pendent vectors
},...,,{
21 t
TTTT = of
E
such that,
given any
t -linearly independent
set
},...,,{
21 t
A
α
α
α
= of vectors in E, the set
T
can
easily be obtained from
A
. We call the set
T
as the
characteristic set of
E. For example, suppose
that
3,4
== tm
, having any three vectors
E∈
321
,,
α
α
α
which do not lie in a plane, E is
totally known with respect to
V . But the idea is to
find 3 special vectors
},,{
321
TTTT
=
in which T
could easily and uniquely be obtained from any
arbitrary and linearly independent set of 3 vectors
in
E.
By the method of finding the row-equivalent
matrix (Hoffman et al., 1971), the characteristic set
of any subspace can easily be found.
Lemma 1: Every matrix
nm
Z
×
has a
unique row-equivalent matrix
nm
T
×
.
Proof: (Hoffman et al., 1971).
Lemma 2: The row space of a matrix is the linear
space spanned by its rows as vectors. The row space
of a matrix and its row-equivalent matrix are the
same. Also, the row spaces of two matrices are the
same if and only if their row equivalent matrices are
the same. As a result, the row equivalent matrix of
all the matrices with the same row spaces is the
same.
Proof: (Hoffman et al., 1971).
So, representing the vectors of
V in the stan-
dard coordinates, the characteristic set of any
t
-
dimensional subspace
E can be found as fol-
lows:
Step 1 Choose an arbitrary base
(
t
α
α
α
,...,,
21
) for E .
Step 2 Generate the matrix
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎣
⎡
=
×
t
mt
Z
α
α
α
#
2
1
in which the
th
i row
of
mt
Z
×
is
i
α
( ti ~1= ).
Step 3 Compute the row-equivalent matrix
(
mt
T
×
) of
mt
Z
×
.
Step 4 According to Lemma 2, the rows
of
mt
T
×
span E and
mt
T
×
is uniquely found. We call
mt
T
×
the characteristic
matrix of
E .So the collection of
rows of the characteris-
tic matrix of
E is also its character-
istic set.
So, if by some means the secret
S is fitted
into a matrix
mt
T
×
which is the row equivalent of
itself, then by choosing each participant’s share as a
vector in
E
(
mt
T
×
is the characteristic matrix of
E
),with the property that every
t
shares are line-
arly independent, we are done.
A NEW (t,n) MULTI-SECRET SHARING SCHEME BASED ON LINEAR ALGEBRA
445
3.2 Description of our Scheme
First, we describe the algorithm for sharing one
secret, and then the multi-secret sharing algorithm is
described. We assume that the secret
S is a binary
data of size
S
.Also, the computations are per-
formed in
)2(
m
GF (there is no limitation on m but
of course for security purposes
m is chosen large
enough).
Step 1 By adding sufficient number of
zeros at the end of
S
,
S
is divided into
t
sub-secrets
i
S ( ti ~1= ) . The
size of each sub-secret is
)1( +
⎥
⎥
⎦
⎤
⎢
⎢
⎣
⎡
=
t
S
S
i
.
Step 2 Sufficient number of zeros are
added to the end of each
i
S . Then, each
i
S is divided
into blocks
ji
S
,
(
)1
)1(
(~1 +
⎥
⎥
⎦
⎤
⎢
⎢
⎣
⎡
−
==
m
S
cj
i
) of
length
1−m . So each
i
S
(
ti ~1= ) is a vector as follows:
) ,...,, (
,2,1, ciiii
SSSS =
(3)
Step 3 Let
T
be a matrix
[
IT
ctt
=
+× )(
]
S ,
where
I
is an identity
t
t
× matrix and
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎣
⎡
=
t
S
S
S
S
#
2
1
is a
c
t
× matrix in which the
th
i row is
i
S
. Obviously,
T
is row-
equivalent of itself so
the rank of
T
is
t
, and
T
is the
characteristic matrix
of the space spanned by its rows
(
E
).
Step 4 The share for the
th
i participant
(
ni ~1= , where n is the
number of participants) is a vec-
tor
E
i
∈
α
. The nec-
essary property for the set
{}
n
A
α
α
α
,...,,
21
= is that any
arbitrary collection
B of
t
vec-
tors in
A
is a line-
arly independent set and as men-
tioned in section 3.1,
T
(therefore
E ) can be easily
computed from
B . To
generate the
i
α
s , one method is
to generate the matrix
TPA
ctn
×=
+× )(
, where
[
]
)1)(1( −−
×
=
ji
tn
gP
(
njti ~1,~1 =
=
)
(
g
is a primitive element in
)2(
m
GF ) and let
i
α
be the
th
i
row of
A
. It is proved in sec-
tion 3.3 that the
i
α
s
generated in this method have
the above mentioned
property (when
12 −≤
m
n ).
Step 5 The secret holder randomly selects
n
ss ,...,
1
as partici-
pants’ secret shadows. Also the
secret holder randomly
selects
r
and computes ),(
i
srf for
each participant.
Step 6 Each participant’s share (
i
α
) is
encrypted with
),(
i
srf
as the key(for example by those
in (Elgamal, 1985),(Rivest et al., 1978)) and each
participant’s public share (
i
β
) is
generated.
Step 7 Publish
),...,,,(
21 n
r
β
β
β
in an au-
thenticated manner.
Secret reconstruction: In order to reconstruct
the secret,
t
participants poll their pseudo shadow
),(
i
srf s. Using the pseudo shadows, the respective
public shares (
i
β
) are deciphered and
i
α
s are gen-
erated. By the use of
t
vectors (
i
α
) and according
to section 3.1 the characteristic matrix
T
, and as a
result, the secret
S are generated.
According to step 1 the secret is first divided
into
t
parts. So, our one-secret threshold scheme is
already a multi-secret threshold scheme with
t
se-
crets. For having the general multi-secret threshold
scheme, we first perform steps 1 and 2 for each of
the
p secrets individually. But in step 3, for gener-
ating the
th
i row of matrix S , the
th
i sub-secrets
of each
p secret are put together in a vector which
is the
th
i row of matrix S . The other steps are the
SECRYPT 2006 - INTERNATIONAL CONFERENCE ON SECURITY AND CRYPTOGRAPHY
446
same. The reconstruction of the secrets is also simi-
lar. Therefore, when matrix
T
is found, the matrix
S and each of the p secrets are easily recon-
structed.
3.3 Bounds on the Maximum Value
of n
As mentioned in section 3.2 The public share for the
th
i participant ( ni ~1= ) is a vector E
i
∈
α
. A
necessary property for the set
{}
n
A
α
α
α
,...,,
21
= is
that any arbitrary collection
B of
t
vectors in
A
is
a linearly independent set. Therefore, the problem of
finding maximum number of the users is equivalent
to finding the maximum possible cardinality of
set
A
. The members of the characteristic set of
E
form a basis for it. For each set
{}
t
zzzB ,...,,
21
= of vectors in,
E
we have
∑
=
=
t
j
jjii
Tz
1
,
γ
where
)2(
,
m
ji
GF∈
γ
(4)
Definition 2 for each Ez
i
∈ the vector
),...,,(
,2,1, tiii
relative
i
z
γγγ
= is called the relative
vector of
i
z and for each set B , the Matrix
[
]
jitt
Z
,
γ
=
×
( tjti ~1,~1 == ) is called the relative
matrix of set
B .
Obviously
B is a linearly independent set if
and only if its relative matrix is invertible. Let
tn
Q
×
be the matrix in which the
th
i row is the relative
vector of
i
α
(each participant’s share vector), i.e.
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎣
⎡
=
×
relative
n
relative
relative
tn
Q
α
α
α
....
2
1
The problem is equivalent to finding the
maximum number of rows for
tn
Q
×
,or similarly the
maximum cardinality of a set
A
.
Lemma 3:
If )(tf is the maximum cardinal-
ity of set
A over a t dimensional space, then
12)( +≥
m
tf
Proof. Let Q be a t
m
×+ )12( matrix defined as
t
m
P
R
Q
×+
⎥
⎦
⎤
⎢
⎣
⎡
=
)12(
where R is a t×2 matrix
t×
⎥
⎦
⎤
⎢
⎣
⎡
2
1...00
0...01
and
[
]
)1)(1( −−
=
ji
gP
)~1,12~1( tji
m
=−= where
g
is a primitive
element in
)2(
m
GF . So for 12,0 −≤≤
m
ji and
)( ji
≠
we have:
ji
gg ≠ . Therefore, according to
the inevitability of Vandermonde matrix, every set
of
t arbitrary and distinct rows are linearly inde-
pendent. Let
{
}
12
21
,...,,
+
=
mt
qqqQ be the collection
of all rows of
Q respectively. So
12)( +≥
m
tf
Lemma 4: The intersection of any two non-
overlapping hyper planes in a
t
dimensional space is
a
2
−
t dimensional space.
Proof: (Hoffman et al., 1971).
Lemma 5: 12)2( +=
m
f .
Proof. According to Lemma 3,
12)2( +≥
m
f
.
Any vector in
2
))2((
m
GF (the space of all ordered
pairs
),( ba which )2(,
m
GFba ∈ ) is a multiple of a
vector in the set
2
Q , so no new vector can be added
to
2
Q . Also for any other set of vectors, with the
property of linearly independence of any two vec-
tors, there is a one to one correspondence between
the set and a subset of
2
Q (relation: being multiple
of each other). So the proof is complete.
Theorem 1: 12)(12 −+≤≤+ ttf
mm
Proof. Let
{
}
k
λ
λ
λ
,...,,
21
=
Π
be a maximal
set with the properties mentioned above. Let
Ω
be
the linear subspace spanned by
221
,...,,
−t
λ
λ
λ
. Be-
cause of linearly independence of these vectors,
there are two independent vectors, e.g.,
21
,
θ
θ
which
the spanned plane by
21
,
θ
θ
is perpendicular to the
Ω
.Let
Γ
be the family of 1−t dimensional hyper
planes passing
Ω
. Obviously, each hyper plane in
Γ
can at most include one of the vectors in
Π
other than
221
,...,,
−t
λ
λ
λ
. Let Ψ be the family of
projection of such vectors on the plane passing
through
21
,
θ
θ
. Trivially, none of the members of
Ψ
are multiple of each other and also all the members
are non-zero (Lemma 4). So there is a one to one
correspondence between
Γ
and Ψ and according to
the proof of lemma 5, there is a one to one corre-
spondence between
Ψ
and a subset of
2
Q . So:
)2(f≤Γ=Ψ
Therefore, we have:
A NEW (t,n) MULTI-SECRET SHARING SCHEME BASED ON LINEAR ALGEBRA
447
2)2( −+≤Π tf
(5)
From (5) and lemma 5:
12)( −+≤Π≤ ttf
m
(6)
Finally, from Lemma 3 and (6) we get the result.
3.4 Cheater Identification and
Security Analysis
It is important for any secret sharing scheme to de-
tect cheating and to identify the cheater. There are
numerous works on this issue such as in Hwang et
al., 1999), (Tan et al., 1999). Therefore, we will not
address this issue here. However, in order to keep
the participants’ shadows secret after the cheater
identification process, there are some points, which
should be mentioned: The secret holder should use
the pseudo shadows
),(
i
srf instead of the real
shadows in generating the public values for cheater
identification. At the same time, with no knowledge
of the real shadows, the verifier should be able to
use the pseudo shadows in order to determine the
existence of a cheater. Hence, in the cheater identifi-
cation process, each participant polls his pseudo
shadow. Therefore, the real shadows will not be
disclosed by the properties of the one-way two-
variable function.
The security of our scheme can be analyzed
from the following different views:
a) Having 1−≤
′
tt pseudo shadows, only t
′
linearly independent vectors from
E
is found. Since
the characteristic set of
E
is determined by comput-
ing the row equivalent matrix
T
, and also in order
to find
T
(
[
IT
ctt
=
+× )(
]
S
), using t
′
vectors
would give no information about matrix
S in which
the secrets are stored. Because every new vector
from the remaining
tt
′
− vectors has a direct impact
on each element of
S .
b) Our scheme will not disclose the partici-
pant’s real shadows
i
s even after multiple secret
reconstruction. Even though pseudo shadows
),(
i
srf have been exposed among many co-
operating participants, the real shadows are well
protected by the properties of the one-way two-
variable function. Therefore in order to share next
p secrets, the secret holder only needs to randomly
choose a new integer
r
without redistributing every
participant’s secret shadow
i
s .
c) Given the public values ),...,,,(
21 n
r
β
β
β
,
an adversary has no way of determining
i
α
’s, with-
out having the pseudo shadows
),(
i
srf (as the
keys). Furthermore, encryption of less than
t
of the
i
β
s, according to part a, shall give no information
about the secrets.
4 PERFORMANCE
COMPARISON
In this section, we will shortly compare the perform-
ance of our scheme with other schemes, especially
Chien’s scheme.
In Chien’s scheme, the secret reconstruction
costs solving the simultaneous
)( tpn −+ linear
equations, while in our scheme, the dependence of
reconstruction process on
n is totally omitted.
Therefore, in the cases where
n is a relatively large
number, our scheme would be more efficient.
In our scheme the computations are performed
in
)2(
m
GF
where
m
2
could be smaller than the
secrets (if their decimal representation is as-
sumed). This would reduce the number of computa-
tional bit operations in some cases. For example,
according to (Koblitz, 1998) in a finite
field
)(
m
pGF , two elements can be divided or mul-
tiplied in
)(ln
2
qO (
m
pq = ) bit operations, and
one element can be raised to the
th
N power in
)))(ln((ln
2
qNO bit operations. So, obviously,
when
)ln(q is reduced by the factor
k
, the opera-
tions are reduced by the factor
2
k . In our scheme,
(for simplicity, suppose one secret threshold
scheme) we approximately (in step 2) reduced the
binary size of the field order (
)(log
2
q ) by
tm
S
and
instead there are
m
S
parallel processes (for each
block in each secret). So since the reduction in
each multiplication or division is by the factor
2
k (as defined above), a total reduction in the com-
putations is expected.
SECRYPT 2006 - INTERNATIONAL CONFERENCE ON SECURITY AND CRYPTOGRAPHY
448
5 CONCLUSION
In this paper, a new ),( nt threshold multi-secret
sharing scheme was proposed. The scheme is
mainly based on vector spaces and matrices and
one-way functions. In this scheme, the computa-
tional complexity is independent of the number of
users .Furthermore, the scheme is a multi-use
scheme which lets the use of conventional cryp-
tographic methods in the secret sharing problem.
REFERENCES
Blakley G.R.: Safeguarding Cryptographic Keys. AFIPS
Conference Proceedings. Vol.48 (1979).pp. 313-317.
Shamir A.: How to Share a Secret. Communications of
ACM .Vol.24 (1979).pp. 612-613.
Deng R.H., Gong L., Lazar A. A., and Guo W.: Authen-
ticated Key Distribution and Secure Broadcast Using
No Conventional Encryption: A Unified Approch
Based on Block Codes. In Proceedings of the IEEE
GLOBE Telecommunication Conference (1995). pp.
1193-1197.
Chien H.-Y., Jan J.-K., and Tseng Y.-M.: An Efficient
Multi-Secret Sharing Scheme. IEICE Transactions on
Fundamentals of Electronic Communications and
Computer Sciences. Vol.E83-A (2000). No. 12. pp.
2762-2765.
Bertilsson M. and Ingemarsson I.: A Construction of
Practical Secret Sharing Schemes Using Linear
Block Codes. In Advances in Cryptology-
Auscrypt’ 92. Springer-Verlag(1992). pp. 2-21.
Karnin E.D., Greene J. W. and Hellman M. E.: On
Secret Sharing Systems. IEEE Transactions on In-
formation Theory, Vol.29 (1983). pp. 35-41.
Hoffman K., Kunze R.: Linear Algebra. Second Edi-
tion. Prentice-Hall. Englewood Cliffs.NJ. (1971)
Pang L., Wang Y.: A New (t, n) Multi-Secret Sharing
Scheme Based on Shamir’s Secret Sharing. Ap-
plied Mathematics and Computation, Vol.167, Nr.2,
(2005). pp. 840-848.
Jackson W. A., Martin K. M. and O’Keefe C. M.: On
Sharing Many Secrets. In Advances in Cryptology-
Asiacrypt’94, Springer-Verlag (1994). pp. 42-54.
He J. and Dawson E.: Multi-Secret Sharing Scheme
Based on One-Way Function. Electronics Letters,
Vol.31. No. 2 (1995) .pp. 93-94.
Elgamal T.: A Public-key Cryptosystem and a Signature
Scheme Based on Discrete Logarithms. IEEE Trans-
actions on Information Theory Vol.31 (1985). pp.
469-472.
Rivest R.L, Shamir A., Adleman L.A: A Method for
Obtaining Digital Signatures and Public-key
cryptosystems. Communications of the ACM,
Vol.21.Nr.2 (1978). pp.120-126.
Hwang R. J., Lee W. B., and Chang C. C.: A Concept of
Designing Cheater Identification Methods for Secret
Sharing. The Journal of Systems and Software.
Vol.46(1999). pp.7-11.
Tan K. J., Zhu H. W. and Gu S. J.: Cheater Identification
in (t, n) Threshold Scheme. Computer Communica-
tions. Vol.22(1999). pp.762-765.
Lin S., Costello D.J.: Error Control Coding. Second
Edition. Prentice Hall.Inc.(2004)
Koblitz N.: Algebraic Aspects of Cryptography. Algo-
rithms and Computation in Mathematics.Vol.3 .
NY. Springer-Verlag.(1998)
A NEW (t,n) MULTI-SECRET SHARING SCHEME BASED ON LINEAR ALGEBRA
449
