IEICE TRANS. FUNDAMENTALS, VOL.E95–A, NO.11 NOVEMBER 2012

2067

PAPER

Secret Sharing Schemes Based on Linear Codes Can Be Precisely
Characterized by the Relative Generalized Hamming Weight
Jun KURIHARA†,††a) , Member, Tomohiko UYEMATSU†b) , Senior Member,and Ryutaroh MATSUMOTO†,†††c) , Member

SUMMARY
This paper precisely characterizes secret sharing schemes
based on arbitrary linear codes by using the relative dimension/length profile (RDLP) and the relative generalized Hamming weight (RGHW). We
first describe the equivocation Δm of the secret vector s = [s1 , . . . , sl ] given
m shares in terms of the RDLP of linear codes. We also characterize two
thresholds t1 and t2 in the secret sharing schemes by the RGHW of linear
codes. One shows that any set of at most t1 shares leaks no information
about s, and the other shows that any set of at least t2 shares uniquely determines s. It is clarified that both characterizations for t1 and t2 are better
than Chen et al.’s ones derived by the regular minimum Hamming weight.
Moreover, this paper characterizes the strong security in secret sharing
schemes based on linear codes, by generalizing the definition of stronglysecure threshold ramp schemes. We define a secret sharing scheme achieving the α -strong security as the one such that the mutual information between any r elements of (s1 , . . ., sl ) and any α − r + 1 shares is always zero.
Then, it is clarified that secret sharing schemes based on linear codes canalways achieve the α -strong security where the value α is precisely characterized by the RGHW.
key words: secret sharing scheme, linear code, relative generalized Hamming weight, relative dimension/length profile

1.

Introduction

Secret sharing scheme [2], [15] is a process of encoding
a secret s into a set of n pieces of information segments(called shares) in such a way that only certain subsetsof them can determine s. The collection of subsets thatcan determine s is called the access structure of the secret sharing scheme. An element in the access structure
is called qualified set, otherwise, nonqualified set. Secretsharing schemes typically have the following complementary thresholds t1 ,t2 (≤ n): (1) any set of at most t1 sharesleaks no information of the secret, and (2) any set of at least
t2 shares is qualified set. When the secret sharing scheme
satisfies t1 + 1 = t2 , the scheme is called a secret sharing
scheme with the (t2 , n)-threshold access structure or (t2 , n)threshold scheme. Shamir’s scheme [15] is based on interManuscript received December 28, 2011.
Manuscript revised July 23, 2012.
† The authors are with the Department of Communications andIntegrated Systems, Tokyo Institute of Technology, Tokyo, 1528550 Japan.
†† The author is with KDDI R&D Laboratories, Inc., Fujiminoshi, 356-8502 Japan.
††† The author is with the Department of Mathematical Sciences,
Aalborg University, Denmark.
a) E-mail: kurihara@kddilabs.jpb) E-mail: uyematsu@ieee.orgc) E-mail: ryutaroh@rmatsumoto.org
DOI: 10.1587/transfun.E95.A.2067

polation of a (t2 − 1)-degree polynomial, and it is known asa typical (t2 , n)-threshold scheme.
McEliece et al. [12] first investigated the relation between linear codes and secret sharing schemes. They
pointed out that shares in Shamir’s threshold scheme [15]can be viewed as symbols of a codeword in Reed-Solomoncode [10]. Piepryzk et al. [14] clarified that threshold
schemes can be constructed from maximum distance separable (MDS) codes [10]. Massey [11] extended McEliece etal.’s construction to those based on general linear codes C ,and demonstrated that there exists a relationship between aqualified set and a codeword in the dual code C ⊥ of C . Duursma et al. [6] gave another construction of secret sharing
schemes which use a linear code C and its subcode C  ⊂ Cwith dim (C /C  ) = 1 to encode s into shares. Moreover,they characterized the thresholds t1 ,t2 in their scheme by theminimum distance of the collection of cosets C /C  , called
coset distance.
On the other hand, since regular (t2 , n)-threshold
schemes generate shares from a secret scalar s, i.e., an element of a field F, Blakley [1] and Yamamoto [18] generalized (t2 , n)-threshold schemes for an l-dimensional vector s = [s1 , . . . , sl ] ∈ Fl (1 ≤ l ≤ t2 − 1). Their schemes
are called (t2 , l, n)-threshold ramp schemes, and realize ltimes smaller bit-size of each share than regular (t2 , n)threshold schemes. In (t2 , l, n)-threshold schemes, there
exists a trade-off between the size of each share and theamount of information leaked from nonqualified sets according to l. Namely, the thresholds t1 ,t2 satisfy t1 + l = t2 ,and i/l (i = 1, . . . , l − 1) of Shannon entropy about s leaks
from any set of t1 + i shares. Yamamoto [18] classified
threshold ramp schemes into two classes. One is weaklysecure schemes, and the other is strongly-secure schemes.
In the case of weakly-secure schemes, some elements of smight leak out deterministically from a set whose cardinality is smaller than t2 . In contrast, strongly-secure schemes
guarantee that no information about a tuple (si : i ∈ I )for any I ⊆ {1, . . . , l} can be obtained from any t2 − |I |shares. Hence, strongly-secure schemes are more securethan weakly-secure schemes. Threshold ramp schemes canbe constructed by using MDS codes as well as regularthreshold schemes. Nishiara et al. [13] proposed a stronglysecure threshold ramp schemes based on a polynomial interpolation. Their scheme employs a systematic MDS codetransformed from a Reed-Solomon code.
Chen et al. [4] extended threshold ramp schemes, andc 2012 The Institute of Electronics, Information and Communication Engineers
Copyright IEICE TRANS. FUNDAMENTALS, VOL.E95–A, NO.11 NOVEMBER 2012

2068
Table 1[4, Sect. 4.1]
[4, Sect. 4.2]
[6]
Theorem 9

Table 2
[8]
Theorem 19

Comparison of characterizations for thresholds t1 ,t2 .

Characterization methodby minimum Hamming weightby minimum Hamming weightby coset distanceby RGHW

Tightness of the characterization
not tight (Proposition 15, Example 16)
not tight (Proposition 12, Example 14)
tight (only for a scalar secret)always tightComparison of characterizations for the α -strong security.

Characterization methodby minimum Hamming weightby RGHW

proposed two secret sharing schemes based on arbitrary linear codes. Namely, one given in [4, Sect. 4.1] is a simple
extension of Massey’s construction for an l-dimensional secret vector s. The other called more fruitful approach in [4,Sect. 4.2] can be also viewed as a generalization of Duursma
et al.’s construction [6] for s. Later, Subramanian et al. [16]proposed a nested coding scheme over the erasure-erasure
wiretap channel, which can be viewed as the same secretsharing scheme as Chen et al.’s more fruitful approach. By
the minimum Hamming weight of linear codes, Chen et al.
characterized thresholds t1 and t2 in each of their two constructions, respectively. However, these characterizations
are loose, i.e., they do not always describe the maximum
possible value of t1 and the minimum possible value of t2
in their schemes. Also, the information leaked from morethan t1 shares was not precisely analyzed. That is, no precise characterization of secret sharing schemes based on arbitrary linear codes has been presented yet.
The first aim of this paper is to characterize secret sharing schemes based on general linear codes precisely. We
give a formal definition of secret sharing schemes basedon linear codes by a linear code D1 , its subcode D2 , andtheir punctured codes C1 and C2 . Our definition includes
Massey’s construction [11], Duursma et al.’s one [6] andboth of Chen et al.’s two constructions [4]. We precisely
characterize the minimum uncertainty (called equivocation[17]) of the secret vector given m(≤ n) shares by the relative
dimension/length profile (RDLP) [9] of C1 , C2 or D1 , D2 .
We also derive a new characterization of thresholds t1 and t2
by the relative generalized Hamming weight (RGHW) [9].
Table 1 summarizes the comparison of our characterizationby the RGHW and existing ones by different methods forthresholds t1 ,t2 . Duursma et al.’s characterization by thecoset distance can be viewed as a special case of ours where
the secret is restricted to be an elements of F. Moreover, it isclarified that our characterization by the RGHW always describe the maximum possible t1 and the minimum possible
t2 , unlike Chen et al.’s ones.
The second aim of this paper is to characterize thestrong security in secret sharing schemes based on general linear codes, by generalizing the definition of stronglysecure threshold ramp schemes. We first define an antiaccess set J as a special set of shares, which is a generalized definition of nonqualified sets in strongly-secure ramp

Tightness of the characterization
not tight (Proposition 20, Example 16)
always tightthreshold schemes [18]. An anti-access set J guarantees
that for any I ⊆ {1, . . . , l}, no information about a tuple(si : i ∈ I ) can be obtained from |J | + 1 − |I | shares of
J . We also define a secret sharing scheme achieving the
α -strong security as the one such that all subsets of shareswith cardinality at most α are anti-access sets. We thenclarify that the schemes of Massey [11] and Chen et al. [4,Sect. 4.1] can always achieve the α -strong security wherethe value α is precisely characterized by the RGHW. Table 2 presents the comparison of our characterization by the
RGHW and existing one for the α -strong security. Similar
to the thresholds t1 ,t2 we stated above, it is proved that thecharacterization of α by the RGHW is better than the existing characterization by the minimum Hamming weight [8].
One merit of secret sharing schemes based on arbitrary
linear code is the efficiency in terms of the size of a field F,
since there is a rich variety of long linear codes over F rather
than MDS codes over F. This is because the MDS nature of
the code restricts the maximum possible number of sharesin threshold schemes. In fact, the so-called Main Conjecture
on MDS codes [10, p.327] implies that the length of an MDS
code over F is at most |F| plus a constant (1 or 2). Especially,
the possible length of Reed-Solomon code over F is at most|F| − 1. Hence, in order to generate more than |F| sharesfrom a secret element s ∈ F by an MDS code, the MDS code
must be constructed over a field whose size is larger than |F|.
It is quite inefficient, especially in the case where a secretsharing scheme is used in cryptographic secure computation[4]. In contrast, secret sharing schemes based on long linear
codes can construct such applications efficiently. Then, ourcharacterization precisely determines the property of secretsharing schemes from the parameter of the linear code.
The remainder of this paper is organized as follows.
Sect. 2 introduces basic notations and gives a formal definition of secret sharing schemes based on linear codes. Sect. 3
precisely characterizes the amount of the secret information
leaked from m(≤ n) pieces of shares, and clarifies that ourcharacterization is better than existing researches. Sect. 4
gives the definition of the strong security in secret sharing
schemes. Further, this section reveals the region of the number of shares, in which the strong security can be achieved.
Finally, Sect. 5 concludes this paper.

KURIHARA et al.: SECRET SHARING SCHEMES BASED ON LINEAR CODES

2069

C1 = S + C2 and S ∩ C2 = {0},2.

Preliminary

2.1 Basic Notations
Let H(X) be Shannon’s entropy of a random variable X,
H(X|Y ) be the conditional entropy of X given Y , and I(X;Y )be the mutual information between X and Y [5]. Let F standfor a finite field. Let |X | denote the cardinality of a set X .
For sets X and Y , we denote by X \Y = {x ∈ X : x  Y }the difference of sets X and Y . The Hamming weight of avector x = [x1 , . . . , xn ] ∈ Fn is defined bywt(x) = |{i : xi  0}|.

The Hamming distance between two vectors x = [x1 , . . . , xn ]∈ Fn , y = [y1 , . . . , yn ] ∈ Fn is defined byd(x,y) = |{i : xi  yi }|.
For a linear subspace C ⊆ Fn , the minimum Hamming distance or minimum Hamming weight of C is given byd(C ) = min {d(x,y) :x,y ∈ C ,x y}= min wt(x) :x ∈ C \{0} .
An [n, k, d] linear code C over F is a k-dimensional subspace of Fn , where d = d(C ). A subspace of a code is calleda subcode. For any linear code C , we define its dual codebyC ⊥ = {x ∈ Fn : x ·y = 0, ∀y ∈ C },wherex ·y represents the standard inner product of vectorsxand y.
2.2 Secret Sharing Scheme Based on Linear Codes
In this subsection, we formally define a secret sharing
scheme based on linear codes.
Let A = {1, . . . , N} be a set of indices. For a subset
J ⊆ A and a vector c = [c1 , . . . , cN ] ∈ FN , let PJ (c) be avector of length N, and the t-th component of PJ (c) is ct
if t ∈ J and given by 0 if t  J . For example for J ={1, 3, 5} and c = [1, 1, 0, 1, 1] (N = 5), we have PJ (c) =[1, 0, 0, 0, 1]. The projection or punctured code PJ (C ) of acode C ∈ FN is the map given by
PJ (C ) = PJ (c) :c ∈ C .
Now we define the following secret sharing schemethat generates n shares.
Definition 1 (Secret sharing schemes). Let D1 ⊆ FN bea linear code over F, and D2 ⊂ D1 be a subcode of D1 .
For an index set X ⊆ A = {1, . . . , N} with |X | = n elements, we define the punctured codes C1 = PX (D1 ) andC2 = PX (D2 ). Assume that |X | is chosen in such a waythat C1  C2 . Choose an arbitrary linear code S satisfyingi.e., direct sum. We then write the dimension of the coset
C1 /C2 byl = dim (C1 /C2 ) = dim S .
Let s ∈ Fl be the secret which is assumed to be uniformly
distributed over Fl . To generate n shares, we first choose a
codeword c2 ∈ C2 uniformly at random and independently
from s. Fix an arbitrary isomorphism ψ : Fl → S . Then,
generate a share vector c1 = [c1 , . . . , cN ] = ψ (s) +c2 ∈ C1 ,and send or store each element ci for i ∈ X as a share.
Here we note that C2 ⊂ C1 always holds in this definition. Also note that S can be always chosen, for instanceby completing a basis of C2 to one of C1 .
Let us consider the following case. Assume that N −n < d(D1 ) and N − n = dim D1 − dim D2 . We then write l =dim D1 − dim D2 = N − n, and let X = {l + 1, . . . , l + n}.
Choose ψ in such a way that ([s,0] + ψ (s) +c2 ) ∈ FN is a
codeword of D1 . Then, our definition is equivalent to theone proposed by Massey [11] and Chen et al. [4, Sect. 4.1].
Moreover, the scheme given by Duursma et al. [6] andthe scheme referred to as a more fruitful approach in [4,Sect. 4.2] by Chen et al. are also included in our definition
as the case for X = A , i.e., C1 = D1 and C2 = D2 .
3.

Characterization of Secret Sharing Schemes

This section precisely characterizes the amount of the secret information leaked from m(≤ n) pieces of shares in thesecret sharing scheme given by Definition 1.
3.1 Equivocation of the Secret
Let S be a random variable whose realization is a secret vector s. Let CI = (Ci : i ∈ I ) be a tuple of random variables
for an index set I ⊆ X , where the realization of Ci is ashare ci . Then, the minimum uncertainty of S given m sharesis defined by
Δm =

min

I ⊆X ,|I |=m

H(S|CI ),(1)

which is called equivocation [17]. We will clarify that, in thesecret sharing scheme defined by Definition 1, the equivocation of S is precisely characterized by the relative dimension/length profile (RDLP) [9].
For a subset I of A = {1, . . . , N}, the shortened code
CI of a code C ⊆ FN is defined as the set of all codewords
whose components are all zero outside of I , that is,
CI = {c = [c1 , . . . , cN ] ∈ C : ci = 0 for i  I } .
For example, for J = {2, 3} (N = 3) andC = {[0, 0, 0], [1, 1, 0], [1, 0, 1], [0, 1, 1]},
we have CJ = {[0, 0, 0], [0, 1, 1]}.

IEICE TRANS. FUNDAMENTALS, VOL.E95–A, NO.11 NOVEMBER 2012

2070

The RDLP of C1 and C2 is defined by the maximum
difference of dimension between shortened codes (C1 )Iand (C2 )I as follows.
Definition 2 (Relative dimension/length profile [9]). Let
C1 ∈ FN be a linear code and C2 be a subcode of C1 . The
i-th relative dimension/length profile (RDLP) of C1 and C2
is defined by
Ki (C1 , C2 ) =max

I ⊆A ,|I |=ifrom Definition 2.
Lastly, we will prove the second equality. Forney’s second duality lemma [7, Lemma 2] yields Ci = PX (Di ) =PX ((Di⊥ )⊥ ) = ((Di⊥ )X )⊥ , and hence Ci⊥ = (Di⊥ )X fori = 1, 2. We thus haveΔm = l − Km ((D2⊥ )X , (D1⊥ )X ).


{dim (C1 )I − dim (C2 )I } ,for 0 ≤ i ≤ N.

3.2 Bounds of Thresholds

Remark 3. When C2 = {0} in this definition, the i-th RDLP
Ki (C1 , C2 ) = Ki (C1 , {0}) is equivalent to the i-th regular dimension/length profile [7] of C1 .

Secret sharing schemes typically have the following complementary thresholds t1 ,t2 : (1) any set I ⊆ X of at most
t1 shares offers the mutual information I(S;CI ) = 0, and(2) any set J ⊆ X of at least t2 shares offers the mutual information I(S;CJ ) = H(S). This section clarifies the
maximum value of t1 and minimum value of t2 in the secretsharing scheme of Definition 1 by the relative generalizedHamming weight (RGHW) defined by Luo et al. [9].

Note that, for a code C ⊆ FN and an index set J ⊆ A ,dual codes of a punctured code PJ (C ) and a shortened code
CJ are defined as(PJ (C ))⊥ = {x ∈ PJ (FN ) :x ·y = 0, ∀y ∈ PJ (C )},(CJ )⊥ = {x ∈ PJ (FN ) :x ·y = 0, ∀y ∈ CJ },respectively, i.e., dual codes over PJ (FN ).
Theorem 4 determines the equivocation Δm defined inEq.(1) by the RDLP of C2⊥ and C1⊥ , and also (D2⊥ )X and(D1⊥ )X .
Thereom 4. In the secret sharing scheme defined by Definition 1, the equivocation given m(≤ n) shares is characterized
by the RDLP as follows.
Δm = l − Km C2⊥ , C1⊥= l − Km (D2⊥ )X , (D1⊥ )X .
Proof. Let I ⊆ X be an arbitrary index set with cardinality|I | = m. It is shown by [4, Theorem 10] that we have theconditional entropy of S given CI as follows.
H(S|CI ) = l − dim PI (C1 ) + dim PI (C2 ).

(2)

For a code C ⊆ FN and an index set J ⊆ A , we have
PJ (C ⊥ ) = (CJ )⊥ and hence PJ (C ) = PJ ((C ⊥ )⊥ ) =((C ⊥ )J )⊥ from Forney’s second duality lemma [7, Lemma
2]. Thus, Eq.(2) can be rewritten as
H(S|CI ) = l − dim ((C1⊥ )I )⊥ + dim ((C2⊥ )I )⊥= l − m + dim (C1⊥ )I + m − dim (C2⊥ )I= l − dim (C2⊥ )I + dim (C1⊥ )I .
Recall C1⊥ and C2⊥ are defined as subspaces of PX (FN ) for
an index set X ⊆ A . Hence the equivocation Δm is givenbyΔm = l −max{dim (C2⊥ )I − dim (C1⊥ )I }I ⊆X ,|I |=m= l − Km (C2⊥ , C1⊥ ),Definition 5 (Relative generalized Hamming weight [9]).
Let A = {1, . . . , N}. Let C1 ∈ FN be a linear code and C2
be a subcode of C1 . The i-th relative generalized Hamming
weight (RGHW) of C1 and C2 is defined by
Mi (C1 , C2 ) = min {|I | : dim (C1 )I − dim (C2 )I ≥ i} ,I ⊆Afor 0 ≤ i ≤ dim (C1 /C2 ).
The following proposition given by Luo et al. [9] clarifies the relationship between the RGHW and the RDLP.
Proposition 6 ([9, Proposition 2]). Let A = {1, . . . , N}. Fora linear code C1 ∈ FN and its subcode C2 ⊂ C1 , the i-th
RGHW Mi (C1 , C2 ) is strictly increasing with i. Moreover,M0 (C1 , C2 ) = 0 and
Mi (C1 , C2 ) = min {|I | : dim (C1 )I − dim (C2 )I = i} ,I ⊆A= min {m : Km (C1 , C2 ) = i} ,for 0 ≤ i ≤ dim (C1 /C2 ), where Km (·, ·) is the RDLP definedby Definition 2.
Remark 7. When C2 = {0}, the i-th RGHW Mi (C1 , C2 ) =Mi (C1 , {0}) is equivalent to the i-th regular generalizedHamming weight [17] of C1 .
Remark 8. The first RGHW M1 (C1 , C2 ) of C1 and C2 isequivalent to the coset distance of C1 /C2 , given by Duursma
et al. [6].
We then give the following theorem.
Thereom 9. Consider the secret sharing scheme defined by
Definition 1. Then, for a set I ⊆ X , the mutual information between S and CI satisfies I(S;CI ) = 0 if
|I | ≤ M1 (C2⊥ , C1⊥ ) − 1,

(3)

KURIHARA et al.: SECRET SHARING SCHEMES BASED ON LINEAR CODES

2071

and I(S;CI ) = H(S) if|I | ≥ n − M1 (C1 , C2 ) + 1.

(4)

Proof. For an arbitrary index set I ⊆ X with cardinality|I | = m, the maximum mutual information between S and
CI is expressed by the equivocation from Theorem 4 as follows.
max

I ⊆X ,|I |=m

I(S;CI ) = H(S) −min

I ⊆X ,|I |=m

H(S|CI )= Km (C2⊥ , C1⊥ ).
Hence, from Proposition 6, the smallest index set satisfying
I(S;CI ) = 1 is of size

This implies that I(S;CI ) = 0 whenever Eq.(3) holds.
Next consider the minimum mutual information between S and CI for |I | = m. The relation between the
shortened code and punctured code of a code C ⊆ FN for
an index set J ⊆ A is given by dim C = dim CJ +dim PJ¯ (C ) from Forney’s first duality lemma [7, Lemma1], where J¯ = A \J . Hence, Eq.(2) can be rewritten as(5)

where I¯ = X \I . Thus, the minimum mutual information
is given bymin

I ⊆X ,|I |=m

=l−
=l−

max

I ⊆X ,|I |=mmax

I ⊆X ,|I |=mmax

Note that the size of smallest index set I satisfying I(S;CI ) = l is Ml (C2⊥ , C1⊥ ), since dim C2⊥ −dim C1⊥ = dim C1 − dim C2 = l from Definition 1. Then,
Ml (C2⊥ , C1⊥ ) ≤ n always holds from Definition 5. Thus thesecret vector s can always be reconstructed from some subsets of shares in the secret sharing scheme.

Here we clarify that our bounds given in Theorem 9 aretighter than the ones of existing results.
First, consider the case of X = A , i.e., D1 = C1 andD2 = C2 , in the secret sharing scheme defined in Definition 1. Then, the scheme is equivalent to that of Duursma etal. [6] and the one referred to as a more fruitful approach in[4, Sect. 4.2]. For this case, Chen et al. proved in [4, Corollary 4] that any index set I ⊆ X offers I(S;CI ) = 0 if
|I | ≤ d(C2⊥ ) − 1,
and I(S;CI ) = H(S) if|I | ≥ n − d(C1 ) + 1.

I(S;CI )= H(S) −Corollary 11. In Definition 1, assume that s ∈ Fl is chosen
according to an arbitrary distribution over Fl and independently from c2 . Even in this case, Theorem 9 still holds.

3.2.1 Comparison with Existing Resultsmin{m : Km (C2⊥ , C1⊥ ) = 1} = M1 (C2⊥ , C1⊥ ).

H(S|CI ) = dim (C1 )I¯ − dim (C2 )I¯ ,Although we have assumed, in Definition 1, that s is
uniformly distributed over Fl , the following corollary immediately follows from [3, Lemma 2, Theorem 3].

Although Chen et al. [4] mentioned that these bounds are nottight, they did not show any evidence.

H(S|CI ){dim (C1 )I¯ − dim (C2 )I¯ }I¯⊆X ,|I¯|=n−m{dim (C1 )I¯ − dim (C2 )I¯ }= l − Kn−m (C1 , C2 ).
From Proposition 6, we thus have the largest index set I
satisfying I(S;CI ) = l − 1 is of sizemax {m : Kn−m (C1 , C2 ) = 1}
= max {n − m : Km (C1 , C2 ) = 1}
= n − min {m : Km (C1 , C2 ) = 1}
= n − M1 (C1 , C2 ).
This implies that I(S;CI ) = 0 whenever Eq.(4) holds.

Remark 10. Eq.(5) is the same equation as [16, Eq. (4)]derived by Subramanian et al.
The thresholds given by the right-hand side of Eq.(3)and Eq.(4) in Theorem 9 are always tight. This is because the proof of Theorem 9 also reveals that there exist index sets I ⊆ X with |I | = M1 (C2⊥ , C1⊥ ) satisfying
I(S;CI ) = 1 and J ⊆ X with |J | = n − M1 (C1 , C2 ) satisfying I(S;CJ ) = l − 1.

Proposition 12. Assume that X = A in the secret sharing
scheme defined by Definition 1. Then, thresholds given by
the right-hand side of Eq.(3) and Eq.(4) in Theorem 9 satisfy
M1 (C2⊥ , C1⊥ ) − 1 ≥ d(C2⊥ ) − 1 and n − M1 (C1 , C2 ) + 1 ≤n − d(C1 ) + 1, respectively.
Proof. From the definition of the RGHW (Definition 5),
we always have M1 (C1 , C2 ) ≥ M1 (C1 , {0}). Recall that thefirst generalized Hamming weight [17] of C1 is representedby M1 (C1 , {0}) from Remark 7. Since the first generalized Hamming weight is the minimum Hamming weight[17], we have d(C1 ) = M1 (C1 , {0}). Thus, M1 (C1 , C2 ) ≥d(C1 ) always holds. Similarly, we have M1 (C2⊥ , C1⊥ ) ≥M1 (C2⊥ , {0}) = d(C2⊥ ). These establish |I | > n − d(C1 ) ≥n − M1 (C1 , C2 ) for the threshold of I(S;CI ) = H(S), and|I | < d(C2⊥ ) ≤ M1 (C2⊥ , C1⊥ ) for that of I(S;CI ) = 0, respectively.
Remark 13. The scheme of Duursma et al. is equivalent tothe case of l = dim C1 − dim C2 = 1. The bounds derived by
the coset distance in [6, Corollary 1.7] is equivalent to ourbounds of Theorem 9 for l = 1.
The next example shows that [4, Corollary 4] is nottight.

IEICE TRANS. FUNDAMENTALS, VOL.E95–A, NO.11 NOVEMBER 2012

2072

Example 14 ([9, p.1227]). Let C1 be a binary linear codewith generator matrix G1 and C2 ⊂ C1 be a subcode with agenerator matrix G2 , where⎡⎤0 0 1 1 1
1 0 1 0 0
G1 = ⎣1 0 1 0 0⎦ and G2 =.
0 1 0 1 0
0 1 0 1 0

symbols of each codeword in D1 , we have d(C1 ) ≥ d(D1 ) −l. On the other hand, M1 (C1 , C2 ) ≥ d(C1 ) holds since d(C1 )can be represented by d(C1 ) = M1 (C1 , {0}). We thus obtain

Then, d(C1 ) = 2 and K2 (C1 , C2 ) = 0. Since the RDLP ismonotonically increasing, M1 (C1 , C2 ) > 2 holds. We thus
have M1 (C1 , C2 ) > d(C1 ).

Example 14 gives a case satisfying the inequality n +l − d(D1 ) + 1 ≥ n − d(C1 ) + 1 > n − M1 (C1 , C2 ) + 1, andthe following example shows a case satisfying the inequalityd(D1⊥ ) − l − 1 < M1 (C2⊥ , C1⊥ ) − 1 in Proposition 15.

Next, consider the following case of Definition 1. Assume that N − n < d(D1 ) and N − n = dim D1 − dim D2 .
We then write l = dim D1 − dim D2 = N − n, and let X ={l + 1, . . . , l + n}. Choose ψ in such a way that ([s,0] +ψ (s) +c2 ) ∈ FN is a codeword of D1 . Then, this case isequivalent to the one proposed by Massey [11] and Chenet al. [4, Sect. 4.1]. We note that dim D1 = dim C1 anddim D2 = dim C2 since N − n < d(D1 ), and that such ψ always exists. For this case, Chen et al. characterized in [4,Sect. 4.1] that any index set I ⊆ X offers I(S;CI ) = 0 if
|I | ≤ d(D1⊥ ) − l − 1,
and I(S;CI ) = H(S) if|I | ≥ n + l − d(D1 ) + 1.
The following proposition proves that these bounds are nottight.
Proposition 15. Assume that N − n < d(D1 ) and l = N −n = dim D1 − dim D2 in the secret sharing scheme definedby Definition 1. Let X = {l + 1, . . . , l + n}, and let ψ bechosen such that ([s,0] + ψ (s) +c2 ) ∈ D1 . Then, thresholds given by the right-hand side of Eq.(3) and Eq.(4) in
Theorem 9 satisfy M1 (C2⊥ , C1⊥ ) − 1 ≥ d(D1⊥ ) − l − 1 andn − M1 (C1 , C2 ) + 1 ≤ n + l − d(D1 ) + 1, respectively.
Proof. First, we prove M1 (C2⊥ , C1⊥ ) − 1 ≥ d(D1⊥ ) − l − 1.
Let G ∈ Fdim D1 ×N be a generator matrix of D1 . Then, thefirst l columns of G and arbitrary d(D1⊥ ) − l − 1 columns
chosen from the last n columns of G always span Fd(D1 )−1 .
This guarantees that I(S;CI ) = 0 if |I | ≤ d(D1⊥ ) − l − 1[4, Sect. 4.1].
Recall that arbitrary d(D1⊥ ) − 1 columns of G are always linearly independent, and some d(D1⊥ ) columns arelinearly dependent [10]. However, in Chen et al.’s proof,
only d(D1⊥ ) − l − 1 columns of d(D1⊥ ) − 1 columns are arbitrary chosen. This implies that, depending on D1 , there
exist cases such that the first l columns of G and arbitraryd(D1⊥ ) − l columns chosen from the last n columns are always linearly independent. Then, I(S;CI ) = 0 if |I | ≤d(D1⊥ ) − l. Hence we have d(D1⊥ ) − l − 1 ≤ M1 (C2⊥ , C1⊥ ) −1 since the threshold given by the right-hand side of Eq.(3)is always tight.
Next we prove n − M1 (C1 , C2 ) + 1 ≤ n + l − d(D1 ) + 1.
Since C1 = PX (D1 ) is generated by puncturing the first l

M1 (C1 , C2 ) ≥ d(C1 ) ≥ d(D1 ) − l.
This establishes n + l − d(D1 ) + 1 ≥ n − M1 (C1 , C2 ) + 1. 

Example 16. Let D1 be a binary linear code with a generator matrix G and a parity check matrix H defined by⎡⎤⎡⎤
100100110100G = ⎣0 1 0 1 1 1⎦ and H = ⎣0 1 0 0 1 0⎦ ,001001011001
respectively. We have d(D1 ) = 2 and d(D1⊥ ) = 2. Let l =1 < d(D1 ) and X = {2, 3, 4, 5, 6}. Then, d(D1⊥ )−l −1 = 0.
However, the first column of G and arbitrary 1 = d(D1⊥ ) −l column chosen from the last 5 columns of G are always
linearly independent. On the other hand, now consider apunctured code C1 = PX (D1 ) with a generator matrix G1
and its subcode C2 with a generator matrix G2 , where⎡⎤
000100010111G1 = ⎣0 1 0 1 1 1⎦ and G2 =.
001001001001Let C2⊥ and C1⊥ be their dual codes with generator matricesG2 and G1 given by⎡⎤
010100010010G2 = ⎣0 1 0 0 1 0⎦ and G1 =,011001011001
respectively. Then, we obtain K2 (C2⊥ , C1⊥ ) = 1 and hence
M1 (C2⊥ , C1⊥ ) = 2. Therefore, M1 (C2⊥ , C1⊥ ) > d(D1⊥ ) − lholds.
4.

Strong Security of Secret Sharing Schemes

This section gives a refined definition of the strong security in secret sharing schemes. Further, we reveal thatthe scheme of Massey [11] and Chen et al. [4] can always
achieve the strong security in the certain range of the number of shares, characterized by the RGHW.
4.1 Definition of the Strong Security
First, we introduce a special subset J of X called ananti-access set. This is the generalized definition of nonqualified sets in strongly-secure threshold ramp schemes,
which is given by Yamamoto [18]. Let a secret vector
be represented by s = [s1 , . . . , sl ], and Si (1 ≤ i ≤ l) beKURIHARA et al.: SECRET SHARING SCHEMES BASED ON LINEAR CODES

2073

a random variable whose realization is si . We denote by
SI = (Si : i ∈ I ) a tuple of random variables for an index
set I ⊆ {1, . . . , l}. Assume that each share ci (i ∈ X ) is
obtained from s as we presented in Sect. 2.1, and S1 , . . . , Sl
are uniformly distributed over F and mutually independent.
We then define an anti-access set as follows.
Definition 17 (Anti-access sets). Let J ⊆ X be an index
set. For any subsets F ⊆ J and E ⊆ {1, . . . , l} with |E | +|F | = |J | + 1, if we haveI(SE ;CF ) = 0,

(6)

J is called an anti-access set.
Now we define the α -strong security of secret sharing
schemes.
Definition 18 (α -strong security). A secret sharing scheme
is called the one achieving α -strong security if all J ⊆ X
with |J | = α are anti-access sets.
Consider the case where the thresholds given by theright-hand side of Eq.(3) and Eq.(4) in Theorem 9 satisfy
M1 (C2⊥ , C1⊥ ) − 1 = dim C2 ,and n − M1 (C1 , C2 ) + 1 = dim C1 ,respectively. This can be attained when both C1 and C2
are maximum distance separable (MDS) codes [10], e.g.,
Reed-Solomon codes. Then, from Theorem 9, the secretsharing scheme defined by Definition 1 is equivalent to a(dim C1 , dim (C2 /C1 ), n)-threshold ramp scheme [1], [18].
Moreover, if the scheme achieves the (dim C1 − 1)-strong
security, i.e., all nonqualified sets are anti-access sets, it iscalled a strongly-secure threshold ramp scheme [13], [18].
4.2 Characterization of the α -Strong Security
This subsection clarifies that the scheme proposed byMassey [11] and Chen et al. [4] can achieve the α -strong
security where the value α is precisely characterized by the
RGHW.
Consider the following case of Definition 1. Assume
that N − n < d(D1 ) and N − n = dim D1 − dim D2 . We
then write l = dim D1 − dim D2 = N − n, and let X ={l + 1, . . . , l + n}. Choose ψ in such a way that ([s,0] +ψ (s) +c2 ) ∈ FN is a codeword of D1 . Then, this case isequivalent to the one proposed by Massey [11] and Chenet al. [4, Sect. 4.1]. We note that dim D1 = dim C1 anddim D2 = dim C2 since N − n < d(D1 ), and that such ψ always exists.
Without any loss of generality, we suppose that D1 isa systematic code. In other words, a generator matrix G1 of
D1 is defined by the systematic form,
G1 = I P ∈ Fdim D1 ×N ,where I is an identity matrix. Also, a generator matrix G2 of

D2 consists of last dim D2 rows of G1 . Under these suppositions, we have the following theorem.
Thereom 19. Assume N − n < d(D1 ) and l = N − n =dim D1 − dim D2 in the secret sharing scheme defined by

Definition 1. Let X = {l + 1, . . . , l + n} ⊂ A , and let ψ
be chosen such that ([s,0] + ψ (s) +c2 ) ∈ D1 . Let Yi ={1, . . . , l + n}\{i} be another index set for 1 ≤ i ≤ l, and define a punctured code G1,i = PYi (D1 ) and a shortened code
G2,i = (D1 )Yi . Then, the secret sharing scheme defined by
Definition 1 can achieve the α -strong security for⊥⊥
α = min M1 (G2,i, G1,i) : 1 ≤ i ≤ l − 1.
Proof. Since we supposed that a generator matrix G1 of D1
is systematic, the secret sharing scheme generates sharescl+1 , . . . , cl+n by[s1 , . . . , sl , cl+1 , . . . , cl+n ]= [s1 , . . . , sl , rl+1 , . . . , rdim D1 ]G1 ,(7)

where rl+1 , . . . , rdim D1 are chosen from F at random. Thisguarantees that, for each i ∈ {1, . . . , l}, G2,i is a subcode of
G1,i with dimension dim G2,i = dim G1,i − 1 = dim D1 − 1.
We have supposed that s1 , . . . , sl are mutually independent and uniformly distributed over F. Hence, for eachi ∈ {1, . . . , l}, the secret sharing scheme given by Eq.(7)can be viewed as another secret sharing scheme that generates shares s1 , . . . , si−1 , si+1 , . . . , sl , cl+1 , . . . , cl+n from one
secret element si . Namely, a secret sharing scheme with D1 ,subcode G2,i ⊂ D1 , and their punctured codes PYi (D1 ) =G1,i , PYi (G2,i ) = G2,i for an index set Yi . Therefore, Theorem 9 yields that for any index sets R1 ⊆ {1, . . . , l}\{i} and⊥ , G ⊥ )−1,R2 ⊆ {l +1, . . . , l +n} with |R1 |+|R2 | ≤ M1 (G2,i1,iwe have
I(Si ; SR1 ,CR2 ) = 0.

(8)

Next consider the mutual information between a subset of secret elements and a subset of shares. Let E ={k1 , . . . , k|E | } ⊆ {1, . . . , l} and F ⊆ {l + 1, . . . , l + n} be arbitrary index sets. We then haveI(SE ;CF ) = H(Sk1 , . . . , Sk|E | ) − H(Sk1 , . . . , Sk|E | |CF )
|E |

|E |

j=1

j=1

= ∑ H(Sk j ) − ∑ H(Sk j |CF , Sk1 , . . . , Sk j−1 )|E |= ∑ I(Sk j ;CF , Sk1 , . . . , Sk j−1 ),j=1from the chain rule of conditional entropy [5]. Since themutual information is nonnegative, we have I(SE ;CF ) =0 if and only if I(Sk j ;CF , Sk1 , . . . , Sk j−1 ) = 0 for all k j ∈⊥ , G ⊥ ), by substituting i = k ,E . If |E | + |F | ≤ M1 (G2,k
j
1,k j
j
R1 = {k1 , . . . , k j−1 } and R2 = F in Eq.(8), we always haveI(Sk j ;CF , Sk1 , . . . , Sk j−1 ) = 0 for only k j . Thus, for any index
sets E and F satisfying

IEICE TRANS. FUNDAMENTALS, VOL.E95–A, NO.11 NOVEMBER 2012

2074



⊥
⊥
|E | + |F | ≤ min M1 (G2,i, G1,i):1≤i≤l ,we always have I(Sk j ;CF , Sk1 , . . . , Sk j−1 ) = 0 for all k j simultaneously, and hence I(SE ;CF ) = 0 holds. Therefore,
every subset of {l + 1, . . . , l + n} with cardinality at most⊥⊥
α = min M1 (G2,i, G1,i) : 1 ≤ i ≤ l − 1,
is an anti-access set.



The value α in Theorem 19 for the α -strong security is as tight as the bounds in Theorem 9. This is because as follows. Let j ∈ {1, . . . , l} be an elementsatisfy⊥ , G ⊥ ) : 1 ≤ i ≤ l . Then,ing M1 (G2,⊥j , G1,⊥j ) = min M1 (G2,i1,isince the the threshold given by the right-hand side ofEq.(3) in Theorem 9 is tight, there always exists at least
one combination of subsets T1 ⊆ {1, . . . , l}\{ j} and T2 ⊆{l + 1, . . . , l + n} with |T1 | + |T2 | = M1 (G2,⊥j , G1,⊥j ) that satisfy I(S j ; ST1 ,CT2 ) > 0. Hence, there exist subsets of{l + 1, . . . , l + n} with cardinality M1 (G2,⊥j , G1,⊥j ) that do notsatisfy Definition 17.
The thresholds given by Theorem 9 are independent of
the distribution of s as shown in Corollary 11. In contrast,
s must be uniformly distributed over Fl to establish Theorem 19. This is because elements of s need to be treatedas random numbers that are mutually independent and uniformly distributed over F, as shown in the proof of Theorem 19.
It is proved in [8] that the secret sharing scheme withthe same setting as Theorem 19 achieves the (d(D1⊥ )) − 2)strong security. Unlike Theorem 19, this characterization by
the minimum Hamming weight is not tight.
Proposition 20. Assume that N − n < d(D1 ) and l = N −n = dim D1 − dim D2 in the secret sharing scheme definedby Definition 1. Let X = {l + 1, . . . , l + n}, and let ψ
be chosen such that ([s,0] + ψ (s) +c2 ) ∈ D1 . Let Yi ={1, . . . , N}\{i} be another index set for 1 ≤ i ≤ l, and define a punctured code G1,i = PYi (D1 ) and a shortened code
G2,i = (D1 )Yi . Then, we have⊥⊥
, G1,i) : 1 ≤ i ≤ l − 1 ≥ d(D1⊥ ) − 2.
min M1 (G2,iThis can be proved in a similar way to theproof of Proposition 15.
Hence the proof is omitted.  We note that Example
 16 also gives a case of⊥⊥
min M1 (G2,i , G1,i ) : 1 ≤ i ≤ l − 1 > d(D1⊥ ) − 2 for l = 1.
5.

Conclusion

This paper has given a precise characterization of secretsharing schemes based on arbitrary linear codes. We havecharacterized thresholds t1 and t2 by the relative generalizedHamming weight (RGHW). One shows that any set of at
most t1 shares leaks no information about the secret, and theother shows that any set of at least t2 shares uniquely determines the secret. Moreover, this paper has precisely characterized the strong security in secret sharing schemes by
the RGHW, as a generalization of strongly-secure threshold
ramp schemes. These characterizations enable to determine
the property of secret sharing schemes from the parametersof linear codes, when we design systems using secret sharing schemes.
Acknowledgment
The authors would like to thank Dr. Tomohiro Ogawa, associate professor at University of Electro-Communications,for his fruitful comments on the relationship between distribution of the secret and thresholds in secret sharing
schemes. The authors would also like to thank two anonymous reviewers for their helpful comments. This research
was partially supported by the MEXT Grant-in-Aid for Scientific Research (A) No. 23246071, and the Villum Foundation through their VELUX Visiting Professor Programme
2011–2012. A part of this research was done during thethird author’s stay at Department of Mathematical Sciences,
Aalborg University. He greatly appreciates the hospitality
by Prof. O. Geil.
References[1] G.R. Blakley and C. Meadows, “Security of ramp schemes,” Proc.
CRYPTO 1984, ser. Lect. Notes Comput. Sci., vol.196, pp.242–268,
Springer-Verlag, 1984.
[2] G.R. Blakley, “Safeguarding cryptographic keys,” Proc. AFIPS 1979
National Computer Conf., vol.48, pp.313–317, 1979.
[3] C. Blundo, A.D. Santis, and U. Vaccaro, “On secret sharing
schemes,” Inf. Process. Lett., vol.65, no.1, pp.25–32, 1998.
[4] H. Chen, R. Cramer, S. Goldwasser, R. de Haan, andV. Vaikuntanathan, “Secure computation from random error correcting codes,” Proc. EUROCRYPT 2007, ser. Lect. Notes Comput. Sci.,
no.4515, pp.291–310, Springer-Verlag, 2007.
[5] T.M. Cover and J.A. Thomas, Elements of Information Theory,
2nd ed., Wiley-Interscience, 2006.
[6] I.M. Duursma and S. Park, “Coset bounds for algebraic geometriccodes,” Finite Fields and Their Applications, vol.16, no.1, pp.36–
55, 2010.
[7] G.D. Forney, Jr., “Dimension/length profiles and trellis complexity of linear block codes,” IEEE Trans. Inf. Theory, vol.40, no.6,
pp.1741–1752, 1994.
[8] J. Kurihara and T. Uyematsu, “Strongly-secure secret sharing basedon linear codes can be characterized by generalized Hamming
weight,” Proc. 49th Annual Allerton Conference on Communication, Control, and Computing, pp.951–957, Sept. 2011.
[9] Y. Luo, C. Mitrpant, A.J. Han Vinck, and K. Chen, “Some new characters on the wire-tap channel of type II,” IEEE Trans. Inf. Theory,
vol.51, no.3, pp.1222–1229, 2005.
[10] F.J. MacWilliams and N.J.A. Sloane, The Theory of ErrorCorrecting Codes, student revised ed., North-Holland Mathematical
Library, 1977.
[11] J.L. Massey, “Some applications of coding theory in cryptography,”in Codes and Ciphers: Cryptography and Coding IV, pp.33–47,
1995.
[12] R.J. McEliece and D.V. Sarwate, “On sharing secrets and ReedSolomon codes,” Commun. ACM, vol.24, no.9, pp.583–584, 1981.
[13] M. Nishiara and K. Takizawa, “Strongly secure secret sharing

KURIHARA et al.: SECRET SHARING SCHEMES BASED ON LINEAR CODES

2075

scheme with ramp threshold based on Shamir’s polynomial interpolation scheme,” IEICE Trans. Fundamentals (Japanese Edition),
vol.J92-A, no.12, pp.1009–1013, Dec. 2009.
[14] J. Pieprzyk and X.-M. Zhang, “Ideal threshold schemes from MDS
codes,” Proc. 5th Int. Conf. Information Security and Cryptology (ICISC), ser. Lect. Notes Comput. Sci., vol.2587, pp.253–263,
Springer-Verlag, 2002.
[15] A. Shamir, “How to share a secret,” Commun. ACM, vol.22, no.11,
pp.612–613, 1979.
[16] A. Subramanian and S.W. McLaughlin, “MDS codes on the erasureerasure wiretap channel,” arXiv:0902.3286v1, 2009, available at
http://arxiv.org/abs/0902.3286[17] V.K. Wei, “Generalized Hamming weights for linear codes,” IEEE
Trans. Inf. Theory, vol.37, no.5, pp.1412–1418, 1991.
[18] H. Yamamoto, “On secret sharing systems using (k, L, n) threshold
scheme,” IEICE Trans. Fundamentals (Japanese Edition), vol.J68-A,
no.9, pp.945–952, Sept. 1985, [English translation: H. Yamamoto,“Secret sharing system using (k, L, n) threshold scheme,” Electron.
Commun. Jpn. Part I, vol.69, no.9, pp.46–54, (Scripta Technica,Inc.), Sept. 1986.].

Jun Kurihara
received the B.E. degree incomputer science and the M.E. degree in communication engineering from Tokyo Institute ofTechnology, Japan, in 2004 and 2006 respectively. He joined KDDI and has been engaged
in the research on information theory, secretsharing and coding theory. He is currently aPh.D. student in the Department of Communications and Integrated Systems at Tokyo Instituteof Technology, and a researcher in KDDI R&DLaboratories, Inc.

Tomohiko Uyematsu
received the B.E.,
M.E. and Dr.Eng. degrees from Tokyo Instituteof Technology in 1982, 1984 and 1988, respectively. From 1984 to 1992, he was with the Department of Electrical and Electronic Engineering of Tokyo Institute of Technology, first as research associate, next as lecturer, and lastly as
associate professor. From 1992 to 1997, he waswith School of Information Science of Japan
Advanced Institute of Science and Technology
as associate professor. Since 1997, he returnedto Tokyo Institute of Technology as associate professor, and currently heis with the Department of Communications and Integrated Systems as professor. In 1992 and 1996, he was a visiting researcher at the Centre National de la Recherche Scientifique, France and Delft University of Technology, Netherlands, respectively. He received the Achievement Awardin 2008, and the Best Paper Award in 1993, 1996, 2002 and 2007 bothfrom IEICE. His current research interests are in the areas of information
theory, especially Shannon theory and multi-terminal information theory.
Dr. Uyematsu is a senior member of IEEE.

Ryutaroh Matsumoto
was born in Nagoya,Japan, on November 29, 1973. He received the
B.E. degree in computer science, the M.E. degree in information processing, and the Ph.D.
degree in electrical and electronic engineering,
all from Tokyo Institute of Technology, Japan,
in 1996, 1998, 2001, respectively. He was an
Assistant Professor from 2001 to 2004, and has
been an Associate Professor since 2004 in the
Department of Communications and Integrated
Systems of Tokyo Institute of Technology. His
research interest includes error-correcting codes, quantum information theory, and communication theory. Dr. Matsumoto received the Young Engineer Award from IEICE and the Ericsson Young Scientist Award from
Ericsson Japan in 2001. He received the Best Paper Awards from IEICE in
2001, 2008 and 2011.