EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS
Vol. 11, No. 2, 2018, 468-475
ISSN 1307-5543 – www.ejpam.com
Published by New York Business Global

A New Approach to Construct Secret Sharing Schemes
Based on Field Extensions

Fatih Molla1, Selda Çalkavur2,∗

1 Engineering of Information Systems, Faculty of Technology, Kocaeli University, Kocaeli,
Turkey
2 Mathematics, Faculty of Arts and Sciences, Kocaeli University, Kocaeli, Turkey

Abstract. Secret sharing has been a subject of study since 1979. It is important that a secret
key, passwords, information of the map of a secret place or an important formula must be kept
secret. The main problem is to divide the secret into pieces instead of storing the whole for a secret
sharing. A secret sharing scheme is a way of distributing a secret among a finite set of people such
that only some distinguished subsets of these subsets can recover the secret. The collection of these
special subsets is called the access structure of the scheme.
In this paper, we propose a new approach to construct secret sharing schemes based on field
extensions.

2010 Mathematics Subject Classifications: 12F05, 94A62.

Key Words and Phrases: Field extension, secret sharing, secret sharing scheme.

1. Introduction

A secret sharing scheme is a method of hiding a secret among several shadows such
that the secret can be retrieved only by some subsets of these shadows. Secret sharing is
useful in many cryptographic applications [2], [17], [18], [5].

There are numerous studies about secret sharing schemes. Several authors have con-
sidered the construction of secret sharing schemes using linear error correcting codes. [4],
[8], [10], [11], [13], [15].

Shamir [17] and Blakley [2] were introduced secret sharing schemes. Massey [10] used
linear codes for secret sharing and explained the relationship between the access structure
and the minimal codewords of the dual code of the underlying code [15], [6].

Another secret sharing scheme is the multisecret-sharing scheme. This scheme was
proposed in [5], [7], [9], [16], [19], [3]. In the multisecret-sharing schemes [9], [16], [1] there
is a set of p secrets can be shared at once and each participant needs to keep one share

∗Corresponding author.

Email addresses: selda.calkavur@kocaeli.edu.tr (S. Çalkavur)
fatih.molla@hotmail.com (F. Molla)

http://www.ejpam.com 468 c© 2018 EJPAM All rights reserved.



F. Molla, S. Çalkavur / Eur. J. Pure Appl. Math, 11 (2) (2018), 468-475 469

is called secret share. In these schemes all p secrets cannot reconstruct. To recover the
secret the participants need to keep one share is called secret share. In these schemes
all p secrets cannot reconstruct. To recover the secret the participants need to submit a
pseudo-share computed from their secret share instead of the secret share itself.

In this work, we present a new approach to construct secret sharing schemes. We use
the system of Shamir’s scheme. So our scheme is a (k, n)-threshold scheme.

The rest of this paper organized as follows. The next section gives the basic prelimi-
naries used in paper. Section III presents secret sharing scheme based on field extensions.
Section IV collects concluding remarks.

2. Background and Preliminaries

In this section we give the basic preliminaries. In this context we remind Shamir’s
secret sharing scheme.

2.1. Shamir’s Secret Sharing Scheme

In a secret sharing scheme, a secret s is divided into n shares and distributed to n
shareholders by a trusted dealer. The shared secret s can only be recovered when k
(k < n) or more than k shares are available. Such a scheme is called a (k, n)-secret
sharing.

In 1979, Shamir introduced a secret sharing scheme. Shamir’s secret sharing scheme is
an effective way to distribute secret to a group of shareholders. Shamir’s scheme is a (k, n)
threshold secret sharing scheme and this scheme was based on polynomial interpolation.

In the Shamir’s secret sharing [17], there are n shareholders P = {P0, P1, . . . , Pn−1}
and a trusted dealer D. We use the shareholders’ IDs (z0, z1, . . . , zn−1) to denote each
participant. Secret is generated and distributed to shareholders by the dealer D se-
cret can be reconstructed based on Lagrange interpolation polynomial by taking any k
shares (αi0 , . . . , αin−1) of participants and their IDs, (zi0 , . . . , zin−1) where {i0, . . . , ik−1} ⊆
{0, 1, . . . , n− 1} [17], [18], [5].

Shamir’s secret sharing scheme provides a method of hiding this secret such that any
k or more participants would be able to reconstruct the original secret but any less than
k participants would not be able to reconstruct the original secret. Assume all the com-
putations are in GF (pm) (n < pm) (p is prime), in which m is the number of bits of the
secret. Shamir’s secret sharing scheme consists of two algorithms [17], [5]:

2.1.1. Share generation algorithm

Construct a polynomial α(z) = s0+s1z+s2z
2+. . .+sk−1z

k−1, where si(i ∈ {0, 1, . . . , k−1})
and z belongs to GF (pm). si(i ∈ {0, 1, . . . , k − 1}) is randomly generated in GF (pm) and
sk−1 is the secret. Each shareholder with ID zi receives a share a(zi) and we assume the
IDs zi are publicly known and unique for each different shareholder. We denote α(zi) as
αi and zij for simplicity in this part.



F. Molla, S. Çalkavur / Eur. J. Pure Appl. Math, 11 (2) (2018), 468-475 470

2.1.2. Secret reconstruction algorithm

For a polynomial of degree k − 1, with knowledge of at least k data points, we can recon-
struct the exact polynomial using Lagrange interpolation in GF (pm) and thus reconstruct
the secret sk−1.

Now we remind some definitions and a proposition associated with subject.

Definition 1. (Minimal access set) A subset of participants is called a minimal access
set, if the participants in the subsets can recover the secret by combining their shares but
any subset at the participants can not do so [14].

Definition 2. (Access structure) The access structure of a secret sharing scheme is the
set of all minimal access sets [14].

3. A Secret Sharing Scheme Based on Field Extensions

In this part we obtain a secret sharing scheme using the some results of [12]. Now
we construct the Shamir’s secret sharing scheme by using a field extension. Consider the
input and output values of secret sharing scheme as the integers. However, we work on
polynomials to do algebraic operations.

Let the number of elements of field extension be q = pm (p is prime and m ∈ Z+). We
choose the secret and IDs of participants from the following set.

Mq = {a | 0 ≤ a ≤ q − 1, a ∈ Z}. (1)

We transform the selected integers to the polynomials of (GF (q))[x] by Algorithm 1.

Algorithm 1.
input: a ∈Mq

output: b ∈ GF (q)
Step 1. a is transformed into vectors of length m with respect to base p.
Step 2. these vectors are written as a polynomial.

Example 1. Consider 5 ∈ M8 ⇒ 5 = (101)2 = θ2 + 1 ∈ GF (8), where θ is a primitive
element of GF (8).

Example 2. Consider 5 ∈ M9 ⇒ 5 = (12)3 = θ + 2 ∈ GF (9), where θ is a primitive
element of GF (9).

We transform the obtained polynomials to the integers by Algorithm 2.

Algorithm 2.
input: b ∈ GF (q)
output: a ∈Mq

Step 1. b is transformed into vectors of length m with respect to base p.
Step 2. these vectors are written with respect to base 10.



F. Molla, S. Çalkavur / Eur. J. Pure Appl. Math, 11 (2) (2018), 468-475 471

Example 3. Consider θ2+1 ∈ GF (8)⇒ θ2+1 = (101)2 = 5 ∈M8, where θ is a primitive
element of GF (8).

Example 4. Consider 2θ + 1 ∈ GF (9) ⇒ 5 = (21)3 = 7 ∈ M9, where θ is a primitive
element of GF (9).

3.1. Proposed Scheme

We consider a polynomial of degree k − 1 as follows.

p(x) =

k−1∑
i=0

aix
i ∈Mq[x], (2)

where the coefficients ai (1 ≤ i ≤ k − 1) are randomly selected. Let the secret be a0
which is a constant term of a polynomial.

This polynomial is written as a polynomial of (GF (q))[x].

t(x) =

k−1∑
i=0

bix
i ∈ (GF (q))[x]. (3)

3.2. Secret Distribution

Let the IDs of participants be u1, u2, · · · , un ∈Mq−{0}. It is obtained the polynomials
of v1, v2, · · · , vn ∈ (GF (q)) by applying Algorithm 1. It is calculated the images of a secret
pieces in GF(q) as follows.

ri = t(vi) ∈ GF (q), (4)

where ri is an image of participant vi (0 ≤ i ≤ k − 1).
By using Algorithm 2, the obtained polynomials are transformed to the integers of

y1, y2, · · · , yn ∈Mq and distributed to the participants.

3.3. Secret Retrieval Procedure

Now we explain how the secret is recovered. Consider a set of W = {d1, d2, · · · , dk}
(d1, d2, · · · , dk ∈ Mq). The elements of W are recovered the secret by combining their
shares.

In the ordered pair (di, yi) (1 ≤ i ≤ k), di is denoted by the identity of participant and
yi is denoted by the secret piece of participant di.

These ordered pairs are transformed to the polynomial pairs (vi, ri) (vi, ri ∈ GF (q))
by using Algorithm 1.

Then the polynomial t(x) is recovered by Lagrange Interpolation and the polynomial
p(x) is obtained by Algorithm 2. So the secret is recovered by using the following equality.

s = p(0) (5)



F. Molla, S. Çalkavur / Eur. J. Pure Appl. Math, 11 (2) (2018), 468-475 472

Note that it is used the Extended Euclid Algorithm to find the multiplicative inverse
of a polynomial with respect to (mod f(x)), where f(x) is the irreducible polynomial of
(GF (p))[x].

Example 5. Assume that GF (23) is the secret space. Let the number of participants be
n = 5, the threshold value be k = 3 and the secret be s = 4. We construct a secret sharing
scheme based on GF (23) with these parameters.

Consider an irreducible polynomial of f(x) = x3 + x+ 1 ∈ (GF (2))[x]. Let θ be a root
of f(x). So the elements of GF (23) are the following.

GF (8) = {0, 1, θ, θ + 1, θ2, θ2 + 1, θ2 + θ, θ2 + θ + 1}.

θ1 = θ
θ2 = θ2

θ3 = θ2 + 1
θ4 = θ2 + θ + 1
θ5 = θ + 1
θ6 = θ2 + θ
θ7 = 1

The relationship between Mq and GF (q) is as follows.

0←→ 0
1←→ 1
2←→ θ
3←→ θ + 1
4←→ θ2

5←→ θ2 + 1
6←→ θ2 + θ
7←→ θ2 + θ + 1

We choose a polynomial in M8[x] to construct the secret pieces.

p(x) = x2 + 5x+ 4 ∈M8[x].

We write the elements of GF (8) corresponding to the coefficients of p(x).

t(x) = x2 + (θ2 + 1)x+ θ2 ∈ (GF (8))[x].

Let the IDs of participants be u1 = 1, u2 = 2, u3 = 3, u4 = 4, u5 = 5 .
These elements correspond to v1 = 1, v2 = θ, v3 = θ + 1, v4 = θ2, v5 = θ2 + 1 in (GF (8))[x].
We obtain the secret pieces as follows.



F. Molla, S. Çalkavur / Eur. J. Pure Appl. Math, 11 (2) (2018), 468-475 473

r1 = t(v1) = t(1) = 0 ⇒ y1 = 0
r2 = t(v2) = t(θ) = θ2 + θ + 1 ⇒ y2 = 7
r3 = t(v3) = t(θ + 1) = θ + 1 ⇒ y3 = 3
r4 = t(v4) = t(θ2) = 0 ⇒ y4 = 0
r5 = t(v5) = t(θ2 + 1) = θ2 ⇒ y5 = 4

The secret will be recovered when 3 participants by combining their shares. We try to
find the secret with participants 2, 4 and 5.

t(x) =
∑
j∈W

yjlj(x),

lj(x) =
∏

m∈W−{j}

x− xm
xj − xm

,

where W = {2, 4, 5}.
Then we obtain the following equation. So we recover the secret in this way.

t(x) = x2 + (θ2 + 1)x+ (θ2) ∈ (GF (8))[x].

p(x) = x2 + 5x+ 4 ∈Mq[x].

s = p(0) = 4.

4. Analysis and Discussion

4.1. Security Analysis

We discuss the security of the proposed (k, n)-secret sharing scheme is as follows.
Introducing more general polynomial

p(x) =
k−1∑
i=0

aix
i ∈Mq[x]

as the polynomial secret in Shamir’s scheme we obtain, a scheme that is not simple to
break the secret. To compute the secret we have to do computation in a field extension.
We use a new approach in the elements of the field extension. That is by finding a primitive
element of the field and then express each its elements as a power of a primitive element.
The secret can be reached every element of field extension Fq (q = pm) can be uniquely
expressed as a polynomial in θ over Fp of degree less then m. So, the access structure of
this scheme is very strong and reliable.



REFERENCES 474

4.2. Performance Analysis

The access structure of this scheme consists of the k elements since the degree of a
polynomial p(x) is k − 1. The possible attack can be explained as follows.

If k− h say, with 1 ≤ h ≤ k participant group together they can guess the secret with
probability 1

h+1 ≤
1
2 .

5. Conclusion

In this present article we obtain a (k, n)-threshold scheme using the elements of field
extension. Our scheme has the same distributed as Shamir’s scheme does. We choose the
secret as an element of Mq and then some participants use the Lagrange Interpolation to
recover the secret.

Moreover, we introduce the access structure of this scheme and consider the possible
attack.

The secret can be recovered only by the some elements of field extension which are
uniquely determined. This means the access structure of this scheme is very strong and
reliable.

References

[1] L Bai, ”A reliable (k,n)-image secret sharing scheme”, Proc. of the 2nd International
Symposium on Dependable, Autonomic and Secure Computing DASC’06, pp.1-6,
1993.

[2] G R Blakley, ”Safeguarding cryptographic keys”, in Proceedings of the 1979 AFIPS
National Computer Conference, vol. 48, pp. 313-317, Jun. 1979.

[3] S Çalkavur, and P Solé, ”Multisecret sharing schemes and bounded distance decoding
of linear codes”, International Journal of Computer Mathematics, vol. 94, issue. 1,
pp. 107-114, 2017.

[4] C Ding, D Kohel, and S Ling, ”Secret sharing with a class of ternary codes”, Theor.
Comp. Sci., vol. 246, pp. 285-298, 2000.

[5] L Harn, and C Lin, ”Detection and identification of cheaters in (t,n) secret sharing
schem”, Des. Codes Cryptography, vol. 52, no. 1, pp. 15-24, Jul. 2009.

[6] L Harn, Comment on ”Multistage secret sharing based on one-way function”, Elec-
tronics Letters, vol. 31(3), pp.262, 1995.

[7] J He, and E Dawson, ”Multistage secret sharing based on one-way function”, Elec-
tronic Letters, vol. 30 (19), pp.1591-1592, 1994.

[8] E D Karnin, J W Greene, and M E Hellman, ”On secret sharing systems”, IEEE
Trans. Inf. Theory, vol.IT-29, no. 1, pp.35-41, Jan. 1983.



REFERENCES 475

[9] H -X Li, C -T Cheng, and L -J Pong, ”A new (t,n) multi-secret sharing scheme”, CIS
2005, vol. 3802, pp. 421-426, 2005.

[10] J L Massey, ”Minimal codewords and secret sharing”, in Proc. 6th Joint Swedish-
Russian Workshop on Information Theory, Mölle Sweden, pp. 276-279, August 1993.

[11] J L Massey, ”Some applications of coding theory”, Cryptography, Codes and Ciphers:
Cryptography and Coding IV, pp. 33-47, 1995.

[12] F Molla, ”A study on the secret image sharing schemes”, Master Thesis, Kocaeli
University, Kocaeli, 2018.

[13] K Okada, and K Kurosawa, ”MDS secret-sharing scheme secure against cheaters”,
IEEE Trans. Inf. Theory, vol. 46, no. 3, pp. 1078-1081, May 2000.

[14] H Özadam, F Özbudak, and Z Saygı, ”Secret sharing schemes and linear codes.”,
Information Security Cryptology Conference with International Participation, Pro-
ceedings, pp. 101-106, 2007.

[15] J Pieprzyk, and X M Zhang, ”Ideal threshold schemes from MDS codes” in Infor-
mation Security and Cryptology Proc. of ICISC 2002 (Lecture Notes in Computer
Science), Berlin, Germany: Springer-Verlag, vol. 2587, pp. 269-279, 2003.

[16] L -J Pong, and Y -M Wang, ”A new (t,n) multi-secret sharing scheme based on
Shamir’s secret sharing”, Applied Math, vol. 167, pp. 840-848, 2005.

[17] A Shamir, ”How to share a secret”, Commun. ACM, vol. 22, no. 11, pp.612-613, Nov.
1979.

[18] A Tompa, and H Woll, ”How to share a secret with cheaters”, in Proceedings on
Advances in cryptology - CRYPTO ’86. London, UK, UK: Springer-Verlag, pp. 261-
265, 1987.

[19] C -C Yang, T -Y Chang, M -S Hwang, ”A (t,n) multisecret sharing scheme”, Applied
Mathematics and Computation, vol. 151, pp. 483-490, 2004.

[20] J Yuan, and C Ding, ”Secret sharing schemes from three classes of linear codes”,
IEEE Trans. on Inf. Theory 52(1): 206-212, Jan. 2006.