# Linear(

Authors: Kenan Kingsley Phiri; Hyunsung Kim
Journal: Security and Communication Networks
 (2019)

---

## Abstract

Threshold secret sharing is concerned with the splitting of a secret inton shares and distributing them to some persons without revealing its information. Any t ≤ n persons possessing the shares have the ability to reconstruct the secret, but any persons less than t cannot do the reconstruction. Linear secret sharing scheme is an important branch of secret sharing. The purpose of this paper is to propose a new polynomial based linear (t, n) secret sharing scheme, which is based on Shamir’s secret sharing scheme and ElGamal cryptosystem. Firstly, we withdraw some required properties of secret sharing scheme after reviewing the related schemes and ElGamal cryptosystem. The designed scheme provides the properties of security for the secret, recoverability of the secret, privacy of the secret, and cheating detection of the forged shares. It has half computation overhead than the previous linear scheme.


---

## Body

## 1. Introduction

Information security has been a major concern over the past years in communication technology. The main concern has been how to make information confidential, authenticating and protecting it from being altered before reaching the receiver. Cryptography is part of the answer to these concerns [1]. The idea in cryptography is to prevent unauthorized use or alteration of information using mathematical tools. In a symmetric cryptosystem, this is achieved by using a shared secret key and in asymmetric cryptosystem it is achieved by using a pair of keys, public and private. The use of secret key or public and private key pair raised another problem of securely storing it. To address this problem, secret sharing schemes allow reliable storage without any risk [2, 3].Threshold secret sharing is a method of splitting a secrets into n shares and distributing them to users such that the shares do not reveal any information about the secret [4]. In this care, the secret is a secret key, which needs to be stored securely. The secret is reconstructed easily if the authorized number of users combines their shares together. A subset of unauthorized users cannot reconstruct the secret or gain any information about the secret. The shares are sent to users using private channels so that each user should not have information of shares of the other users before reconstruction is done. Schemes that achieve this are called secret sharing schemes. Some schemes reveal the shares of all users who take part in secret reconstruction. In such schemes, users know all shares after the secret is reconstructed. This is called open reconstruction. While other schemes do not reveal the shares even after reconstruction is done for the reason that the shares may be reused. This is called closed reconstruction. Such schemes use a trusted third party to take the role of secret reconstruction as discussed by Martin [5].Shamir introduced a (t, n) threshold secret sharing scheme, which provides secure way of sharing a secret [6]. The scheme starts with secret information, which is divided into n pieces of information called shares. The shares are distributed by a dealer to n individuals, called users; each user gets at least a share. These shares do not reveal any information about the secret. The dealer is entrusted with sharing of the secret to n users using share generation and distribution algorithms. No user knows the share of the others because distribution is done through secure channel. The secret is reconstructed by any authorized subset of users with cardinality t using Lagrange interpolation.Tompa and Woll exposed the weakness of Shamir’s scheme by introducing a cheating concept [7]. Malicious users present forged shares during reconstruction so that the honest users get an invalid secret. The cheaters will be able to reconstruct a valid secret since they know all correct shares. Therefore, Shamir’s scheme cannot withstand this attack even if there is only one cheater. Furthermore, they proposed an improved scheme which uses redundant shares to detect cheating so that malicious users are prevented. Redundant shares are extra shares used in reconstructing the secret other than the required threshold. Many schemes also solve the same problem of cheating detection [8–14].Apart from cheating detection, there are schemes that identify cheaters in [15–20]. These schemes provide the method of identifying any forged share once it has been detected that cheating takes place. Identification is also good since it helps to recognize who the cheater is and can be removed from the system during the next sharing. Other schemes reconstruct the secret even though there are forged shares called robust secret sharing scheme (RSS) [21–23]. RSS prevents cheating by allowing the reconstruction of the correct secret even if some participants submit forged shares. However, the probability of recovering the secret in RSS depends on the number of forged shares submitted during reconstruction phase. Furthermore, some schemes verify shares and are called verifiable secret sharing schemes (VSS) [24, 25]. VSS also prevents cheating by verifying the shares received from the dealer. In VSS, users assume that the adversary may corrupt the dealer, as a result it is no longer trusted. Once user receives the share from the dealer, he (or she) shares it to other users and creates a check vector, which helps to identify cheaters. The user rejects the share if it does not agree to the check vector, otherwise accepts it.To achieve cheating prevention, users are given a share of the secret plus additional information, which is used for cheating detection. This makes share size|
v
i
|, ∀
i≤ t - 1, to increase greatly as compared to the secret size. However, it is shown by Carpentier et al. that a lower bound for the problem should be given as |
v
i
|
≥
|
s
| / ε, where ε is the cheating probability [26]. The lower bound is based on the assumption thatt - 1 cheaters somehow know the secret before they cheat a user U
t. This is called Carpentieri, De Santis, and Vaccaro (CDV) assumption. However, Ogata and Kurosawa proposed a scheme that detects cheating based on the assumption that no cheating user knows the secret [27]. The scheme’s share size reaches the lower bound of |
v
i
|
≥ (|
s
| - 1)/ε+1. This is called Ogata, Kurosawa, and Stinson (OKS) assumption.Linear secret sharing schemes have been studied because of their application in multiparty computation and function sharing [28, 29]. The schemes are able to detect cheating behavior of malicious users during reconstruction of the secret; hence, an honest user cannot be fooled. Liu et al.’s scheme could be applied if system needs to share more than one secret [28]. Cramer et al.’s scheme depends its security on the universal hash function, which means that it is not unconditionally secure, where Lin and Harn’s scheme has been proved to be easily broken by a simple attack as pointed out by Ghodosi [30, 31]. Liu et al.’s scheme uses two polynomials to detect cheating during secret reconstruction and reduce the share size given to a user. Use of two polynomials increases the number of computations the scheme undergoes. As a result, there is an increased computation overhead.This paper proposes a new linear (t,n) threshold secret sharing scheme based on a polynomial called polynomial based linear scheme (PBLS), which optimizes the number of computation overhead while maintaining security and privacy concerns. The goals that achieve security and privacy concerns (SP) of PBLS are(i)
SP1: provide security of the secret.
(ii)
SP2: provide recoverability of the secret once shared.
(iii)
SP3: provide privacy of the secret and shares.
(iv)
SP4: provide cheating detection feasibility not only for one cheater but alsot – 1 cheaters so that any malicious behavior could be detected.The goal that achieves computation overhead (CO) of PBLS is(i)
CO: reduce the number of polynomials used so that computational overhead is reduced as compared to Liu et al.’s scheme.To achieve these goals, PBLS uses ElGamal cryptosystem and Shamir’s scheme as core operations. ElGamal cryptosystem helps to design a basic scheme, which is the initialization of PBLS. The basic scheme aims at hiding the secret during share generation phase, which can be revealed during cheating detection. PBLS applies Shamir’s secret sharing scheme to share the secret, which uses the polynomialf
(
x
) such that the element hiding the secret becomes the coefficient of x. Therefore, reconstruction of the secret in PBLS uses Lagrange interpolation, which comes up with the polynomial f
′
(
x
). Revealing the secret helps to detect cheating. PBLS has an advantage over Liu et al.’s scheme in the computation overhead concern. Furthermore, PBLS provides cheating detection feasibility, which is not available in Shamir’s scheme.


## 2. Preliminaries

This section provides some basic mathematical and cryptographic concepts, which are major tools in secret sharing schemes, and reviews related works. First of all, the definition of finite field is provided together with some properties [32–34]. Polynomials in a finite field and Lagrange interpolation are also discussed to give understanding on the concepts. ElGamal cryptosystem is briefly discussed because it is used in construction of basic scheme. After that, we review related works such as linear secret sharing schemes, access structure, and some previous schemes like Shamir’s and Liu et al.’s schemes [6, 14].


### 2.1. Basic Mathematical and Cryptographic Concepts

This section gives an overview of some mathematical concepts, which are useful in secret sharing like finite field, polynomial and Lagrange interpolation. For more details on finite field, refer to [32–34]. The section also gives an overview of ElGamal cryptosystem, which assists in construction of basic scheme.


#### 2.1.1. Finite Field

Definition 1.
A finite fieldF is a finite set on which addition, subtraction, multiplication, and division are defined and the following axioms are satisfied.(1)
Associative: for alla,b, and c in F,a + (b +c) = (a +b) +c anda · (b ·c) = (a ·b) ·c.
(2)
Commutative: for alla andb∈
F,a +b =b +a anda ·b =b ·a.
(3)
Existence of identity: there exists elementse and e
′
∈
F, such thata +e =e +a =a and a
·
e
′ = e
′ ·a =a.
(4)
Existence of inverse: for every elementa ∈
F, there exists an element -a such thata + (-a) =e. Similarly for every elementa ∈
F, there exists an elementa
−1
∈
F such thata ·a
−1 = e
′.
(5)
Distributive: for alla,b, and c in F,a · (b+c) = (a ·b) + (a ·c).
Note that an element -a is called additive inverse and another element is called multiplicative inverse. An element e is an additive identity and an element e
′ is multiplicative identity. In this paper, we takee = 0 and e
′ = 1.Definition 2 (finite field of orderp).
Letp be a prime. The set of integers Z
p = {
0, 1, 2, …,p - 1
} with addition and multiplication performed modulo p is a finite field of order p and is denoted as F
p = Z
p.Proposition 3 (multiplicative inverse).
Letp be a prime. Elementa∈
Z
p,a ≠ 0 has a multiplicative inverseb =a
−1 such thata ·b ≡ 1 m
o
d
p.Definition 4 (group of units).
Letp be a prime. A group F
p
∗ is a set that contains nonzero elements and is called a group of units.


#### 2.1.2. Polynomials over Finite Field

Definition 5 (polynomial overF
p).
LetF
p be a field. Any expression (1)
f
x
=
∑
i
=
0
t
a
i
x
i
a
_
i
_
∈
F
p
,where t is an arbitrary positive integer which is called a polynomial over F
p.Definition 6 (degree of polynomialf(x)).
Given a nonzero polynomialf
x
=
∑
i
=
0
t
a
i
x
i, where a
t ≠ 0, the number t is said to be the degree off(x) denoted as degf(x).Definition 7 (equal polynomials).
Letf
x
=
∑
i
=
0
t
a
i
x
i and f
′
x
=
∑
i
=
0
m
b
i
x
i, where a
t ≠ 0 and b
m ≠ 0 are two polynomials of degrees t andm, respectively. The two polynomials are equal and writef(x) = f
′(x), ift =m and a
i = b
i for alli = {
0, 1, 2, …, t
}.Definition 8 (roots of a polynomial).
An elementα∈
F is called a root off(x) iff(α) = 0.Proposition 9.
A polynomialf
x
=
∑
i
=
0
t
a
i
x
i, a
i
∈
F of degree t cannot have more than t roots in the field F.


#### 2.1.3. Lagrange Interpolation

This is a method of reconstructing a polynomial from given known points. The polynomial constructed by Lagrange interpolation is called Lagrange interpolation polynomial, which is unique. To reconstruct the polynomial of degreet,t + 1 values are required, i.e., (α
i, β
i) for alli = 0, 1, 2, …,t such thatf(α
i) = β
i.Proposition 10.
Letα
ifor alli = 0, 1, 2, …,t be distinct elements ofF and β
ifor alli = 0, 1, 2, …,t be arbitrary elements ofF. There exists no more than one polynomialf(x) of degree at most t such that f(α
i) = β
i for alli = 0, 1, 2, …,t.Theorem 11 (see [33]).
Letα
0, α
1, …, α
t be distinct elements ofF and β
0, β
1, …, β
t be arbitrary elements ofF. There exists a unique polynomial(2)
f
x
=
∑
i
=
1
t
β
i
x
-
α
0
…
x
-
α
i
-
1
x
-
α
i
+
1
…
x
-
α
t
α
i
-
α
0
…
α
i
-
α
i
-
1
α
i
-
α
i
+
1
…
α
i
-
α
tof degree at most t such thatf(α
i) = β
ifor alli = 0, 1, 2, …,t.Proof.
We adopt the proof by Slinko [33]. The polynomial in Equation (2) was constructed as follows. First construct polynomials g
i(x) of degree t such that g
i(α
i) = 1 and g
i(α
j) = 0 fori ≠j. These polynomials are(3)
g
i
x
=
x
-
α
0
…
x
-
α
i
-
1
x
-
α
i
+
1
…
x
-
α
t
α
i
-
α
0
…
α
i
-
α
i
-
1
α
i
-
α
i
+
1
…
α
i
-
α
t
.Thus, the polynomials g
0(x), g
1(x), …, g
t(x) are constructed. Furthermore, we multiply by β
i fori = 0, 1, 2, …,t and obtain the polynomials β
0
g
0(x), β
1
g
1(x), …, β
t
g
t(x). Summing the polynomials β
i
g
i(x) the desired polynomialf(x) is constructed as Equation (4).(4)
f
x
=
∑
i
=
0
t
β
i
g
i
xWe setf(α
i) = β
i as required. This polynomial is unique by Proposition 10.


#### 2.1.4. ElGamal Cryptosystem

ElGamal cryptosystem is in a family of public key cryptography [35]. Public key cryptography uses public key and private key to encrypt and decrypt messages, respectively, such that knowledge of private key makes decryption easy. Without knowing the private key, it is impossible to decrypt a message in acceptable time. Security of ElGamal is based on discrete logarithm problem (DLP). Therefore, an attacker has to solve DLP to decrypt an intercepted message on ElGamal cryptosystem.Definition 12 (finite field DLP (FFDLP)).
Given a finite fieldF
p, a primitive element g of F
p, and a nonzero element b of F
p, the FFDLP of b to baseg, written as logg(b), is determining the least nonnegative integer i such thatd =g
i.Three algorithms are used in ElGamal cryptosystem, which are key generation, encryption, and decryption. We assume Alice and Bob want to communicate over an insecure channel. They have to generate a public and private key pair for encryption and decryption as follows.Key Generation. Bob will do the following steps:(i)
Generate a large primep and a generator g of a multiplicative group Z
p
∗
(ii)
Select a random integerb ∈
Z
p
∗ such that 1 ≤b≤p – 2
(iii)
ComputeY ≡g
b modp.The public key for Bob is (p,g,Y) and b is the private key. Bob publishes the public key so that if anyone wants to send an encrypted message to him, they can use it.Y is an element in Z
p
∗, which has a multiplicative inverse in the group.When Alice wants to send a messageM to Bob, she needs to use Bob’s public key to encrypt the message. The following are the steps she takes:Encryption
(i)
Encode the messageM such that 1 ≤M≤p – 1.
(ii)
Select a random exponentk.
(iii)
ComputeC
1 =g
k and C
2 =M ·Y
k.The encrypted message sent to Bob is a pair (C
1, C
2).Once Bob receives the message, he uses his private key to decrypt it in the following way:Decryption
(i)
ComputeC
1
-
b =g
-bk
(ii)
ComputeM= C
1
-
b · C
2 =g
-bk ·M ·g
bk.The elementC
1
-
b is the multiplicative inverse ofg
bk.


### 2.2. Related Works

This section reviews linear secret sharing schemes, access structure of secret sharing schemes, and some previous schemes like Shamir’s and Liu et al.’s schemes [6, 14]. Furthermore, the section discusses the strong and weak properties of the reviewed schemes.


#### 2.2.1. Linear Secret Sharing Scheme

Linear (t,n) secret sharing scheme is a special type of secret sharing scheme where all the n shares of the secret satisfy a linear relationship [6, 14]. The Definition 13 gives what linear secret sharing scheme is.Definition 13 (linear secret sharing scheme).
A (t,n) secret sharing scheme is a linear secret sharing scheme when the n shares, v
1, v
2, …, v
n can be presented as in Equation (5) (5)
v
1
,
v
2
,
…
,
v
n
=
k
1
,
k
2
,
…
,
k
t
H
,where H is a publict ×n matrix whose anyt ×t submatrix is not singular. The vector (k
1, k
2, …, k
t) is randomly chosen by the dealer.According to Definition13, we can see that Shamir’s (t,n) secret sharing scheme is a linear scheme. Let(6)
f
x
=
a
0
+
a
1
x
+
a
2
x
2
+
…
+
a
t
-
1
x
t
-
1
.The shares v
i =f(i),i = 1, 2, …,n can be presented as in Equation (7)(7)
v
1
,
v
2
,
…
,
v
n
=
a
0
,
a
1
,
a
2
,
…
,
a
t
-
1
H
,where h
i
,
j =j
i1 (h
i
,
j denotes the entry atith row andjth column of matrixH).


#### 2.2.2. Access Structure

Assume thatU is the set of users whereU = {
U
1, U
2, …, U
n
} and D is the dealer who facilitates secret sharing. An access structure is defined as follows.Definition 14 (access structure).
Let 2U be the power set of the set of all users U. The set Γ ⊆ 2U of all authorized coalitions is called the access structure of the secret sharing scheme [33].
If a subset is in the access structure, all sets that contain that subset should also form part of the access structure. LetX and Y be subsets of Γ such thatX⊆ Y. An access structure Γ may be any subset of 2U such that (8)
X
∈
Γ
a
n
d
X
⊆
Y
,
t
h
e
n
Y
∈
Γ
.
The condition in Equation (8) attached to access structure is called monotone property, which shows that if a smaller subset can know the secret, then any other larger set containing the subset will know it too.Definition 15.
Let Γ⊆ 2U be an access structure. A coalitionC⊆ U is called minimal authorized coalition if it is authorized and any proper subset of C is not authorized [33].
For example, ifT⊂ C and C is the minimal authorized coalition, then T is not authorized because |
T
| < |
C
|. The assumption is that every user is in at least one minimal coalition and otherwise is not useful in reconstructing the secret. In a linear (t,n) secret sharing scheme, the minimal coalition has subsets with t users.


#### 2.2.3. Shamir’s (t,n) Threshold Scheme

Shamir proposed a (t,n) threshold scheme that splits a secrets∈ S into n shares, which are distributed to n users [6]. Splitting is done by a dealer using an algorithm called share generation algorithm. The algorithm uses a polynomialf(x) of degreet - 1 to generate and distribute shares. The secret is reconstructed based on interpolating a polynomial using Lagrange interpolation, which is reconstructed by t users. The users combine their shares to reconstruct a polynomial f
′(x) of degree t using reconstruction algorithm. The algorithm inputs the user’s identity i and their share v
i, which forms a point or an ordered pair (i, v
i) for alli = 1, 2, …,t and outputs the secret f
′(0) =s. Shamir’s scheme has the following important properties.(i)
Share size is exactly equal to secret size.
(ii)
If a new player joins or leaves, it is easy to add or delete shares without affecting the other shares.
(iii)
It is easy to change the shares of the same secret just by changing the polynomial without breaching any security.
(iv)
t - 1 users do not reveal any information about the secret.However, Tompa and Woll discovered that the scheme cannot withstand cheating if there is an untrusted user during secret reconstruction [7]. As a result, Shamir’s scheme faces the following challenges during secret reconstruction.(i)
Any malicious user can present a forged share without being noticed.
(ii)
It is difficult to detect if the reconstructed secret is invalid.
(iii)
A malicious user, once is successful in cheating other users, will be able to reconstruct the valid secret.


#### 2.2.4. Cheating Prevention

Cheating prevention in secret sharing became a great concern after Tompa and Woll introduced cheating concept. As a result, many schemes with cheating prevention are proposed where some detect cheating, others identify cheaters, and so on. Some of the categories of cheating prevention are as follows.(i)
Cheating detection: schemes provide the method to detect any forged share submitted for secret reconstruction by malicious user [7, 12]. The assumption is that the dealer is trusted.
(ii)
Cheater identification: schemes provide the method to detect and identify any forged share presented for secret reconstruction by a malicious user [15, 17]. The assumption is that the dealer is trusted.
(iii)
Robust secret sharing: schemes assume the dealer is trusted. Schemes can reconstruct a correct secret even if there are a number of forged shares presented by untrusted user [22].
(iv)
Verifiable secret sharing: schemes assume that the dealer is not trusted. Each user verifies the shares if valid using verification algorithm before reconstruction is done [9, 25].


#### 2.2.5. Liu Et Al.’s Scheme

Liu et al. proposed a linear threshold secret sharing scheme, which is capable of cheating detection with share size|
v
i
| ≥ |
s
| / ε, where ε > 0 is the probability of cheating [14]. Liu et al.’s scheme is a combination of two Shamir’s schemes. Two polynomials are used to share a secret s. Cheating detection is done by finding a random elementr∈
Z
p during secret reconstruction.Liu et al.’s scheme adopts Shamir’s scheme in sharing the secret. This means that most properties of Liu et al.’s scheme are similar to Shamir’s scheme. However, there are some properties, which Shamir’s scheme does not have. The properties include the following.(i)
Share size given to each user is equal to or greater than the secret size, i.e.,|
v
i
| ≥ |
s
| / ε.
(ii)
Detect cheating whenever a forged share is presented during reconstruction.However, the scheme uses two polynomials to achieve the property of cheating detection, which makes number of computations to double as compared to Shamir’s scheme.


## 2.1. Basic Mathematical and Cryptographic Concepts

This section gives an overview of some mathematical concepts, which are useful in secret sharing like finite field, polynomial and Lagrange interpolation. For more details on finite field, refer to [32–34]. The section also gives an overview of ElGamal cryptosystem, which assists in construction of basic scheme.


### 2.1.1. Finite Field

Definition 1.
A finite fieldF is a finite set on which addition, subtraction, multiplication, and division are defined and the following axioms are satisfied.(1)
Associative: for alla,b, and c in F,a + (b +c) = (a +b) +c anda · (b ·c) = (a ·b) ·c.
(2)
Commutative: for alla andb∈
F,a +b =b +a anda ·b =b ·a.
(3)
Existence of identity: there exists elementse and e
′
∈
F, such thata +e =e +a =a and a
·
e
′ = e
′ ·a =a.
(4)
Existence of inverse: for every elementa ∈
F, there exists an element -a such thata + (-a) =e. Similarly for every elementa ∈
F, there exists an elementa
−1
∈
F such thata ·a
−1 = e
′.
(5)
Distributive: for alla,b, and c in F,a · (b+c) = (a ·b) + (a ·c).
Note that an element -a is called additive inverse and another element is called multiplicative inverse. An element e is an additive identity and an element e
′ is multiplicative identity. In this paper, we takee = 0 and e
′ = 1.Definition 2 (finite field of orderp).
Letp be a prime. The set of integers Z
p = {
0, 1, 2, …,p - 1
} with addition and multiplication performed modulo p is a finite field of order p and is denoted as F
p = Z
p.Proposition 3 (multiplicative inverse).
Letp be a prime. Elementa∈
Z
p,a ≠ 0 has a multiplicative inverseb =a
−1 such thata ·b ≡ 1 m
o
d
p.Definition 4 (group of units).
Letp be a prime. A group F
p
∗ is a set that contains nonzero elements and is called a group of units.


### 2.1.2. Polynomials over Finite Field

Definition 5 (polynomial overF
p).
LetF
p be a field. Any expression (1)
f
x
=
∑
i
=
0
t
a
i
x
i
a
_
i
_
∈
F
p
,where t is an arbitrary positive integer which is called a polynomial over F
p.Definition 6 (degree of polynomialf(x)).
Given a nonzero polynomialf
x
=
∑
i
=
0
t
a
i
x
i, where a
t ≠ 0, the number t is said to be the degree off(x) denoted as degf(x).Definition 7 (equal polynomials).
Letf
x
=
∑
i
=
0
t
a
i
x
i and f
′
x
=
∑
i
=
0
m
b
i
x
i, where a
t ≠ 0 and b
m ≠ 0 are two polynomials of degrees t andm, respectively. The two polynomials are equal and writef(x) = f
′(x), ift =m and a
i = b
i for alli = {
0, 1, 2, …, t
}.Definition 8 (roots of a polynomial).
An elementα∈
F is called a root off(x) iff(α) = 0.Proposition 9.
A polynomialf
x
=
∑
i
=
0
t
a
i
x
i, a
i
∈
F of degree t cannot have more than t roots in the field F.


### 2.1.3. Lagrange Interpolation

This is a method of reconstructing a polynomial from given known points. The polynomial constructed by Lagrange interpolation is called Lagrange interpolation polynomial, which is unique. To reconstruct the polynomial of degreet,t + 1 values are required, i.e., (α
i, β
i) for alli = 0, 1, 2, …,t such thatf(α
i) = β
i.Proposition 10.
Letα
ifor alli = 0, 1, 2, …,t be distinct elements ofF and β
ifor alli = 0, 1, 2, …,t be arbitrary elements ofF. There exists no more than one polynomialf(x) of degree at most t such that f(α
i) = β
i for alli = 0, 1, 2, …,t.Theorem 11 (see [33]).
Letα
0, α
1, …, α
t be distinct elements ofF and β
0, β
1, …, β
t be arbitrary elements ofF. There exists a unique polynomial(2)
f
x
=
∑
i
=
1
t
β
i
x
-
α
0
…
x
-
α
i
-
1
x
-
α
i
+
1
…
x
-
α
t
α
i
-
α
0
…
α
i
-
α
i
-
1
α
i
-
α
i
+
1
…
α
i
-
α
tof degree at most t such thatf(α
i) = β
ifor alli = 0, 1, 2, …,t.Proof.
We adopt the proof by Slinko [33]. The polynomial in Equation (2) was constructed as follows. First construct polynomials g
i(x) of degree t such that g
i(α
i) = 1 and g
i(α
j) = 0 fori ≠j. These polynomials are(3)
g
i
x
=
x
-
α
0
…
x
-
α
i
-
1
x
-
α
i
+
1
…
x
-
α
t
α
i
-
α
0
…
α
i
-
α
i
-
1
α
i
-
α
i
+
1
…
α
i
-
α
t
.Thus, the polynomials g
0(x), g
1(x), …, g
t(x) are constructed. Furthermore, we multiply by β
i fori = 0, 1, 2, …,t and obtain the polynomials β
0
g
0(x), β
1
g
1(x), …, β
t
g
t(x). Summing the polynomials β
i
g
i(x) the desired polynomialf(x) is constructed as Equation (4).(4)
f
x
=
∑
i
=
0
t
β
i
g
i
xWe setf(α
i) = β
i as required. This polynomial is unique by Proposition 10.


### 2.1.4. ElGamal Cryptosystem

ElGamal cryptosystem is in a family of public key cryptography [35]. Public key cryptography uses public key and private key to encrypt and decrypt messages, respectively, such that knowledge of private key makes decryption easy. Without knowing the private key, it is impossible to decrypt a message in acceptable time. Security of ElGamal is based on discrete logarithm problem (DLP). Therefore, an attacker has to solve DLP to decrypt an intercepted message on ElGamal cryptosystem.Definition 12 (finite field DLP (FFDLP)).
Given a finite fieldF
p, a primitive element g of F
p, and a nonzero element b of F
p, the FFDLP of b to baseg, written as logg(b), is determining the least nonnegative integer i such thatd =g
i.Three algorithms are used in ElGamal cryptosystem, which are key generation, encryption, and decryption. We assume Alice and Bob want to communicate over an insecure channel. They have to generate a public and private key pair for encryption and decryption as follows.Key Generation. Bob will do the following steps:(i)
Generate a large primep and a generator g of a multiplicative group Z
p
∗
(ii)
Select a random integerb ∈
Z
p
∗ such that 1 ≤b≤p – 2
(iii)
ComputeY ≡g
b modp.The public key for Bob is (p,g,Y) and b is the private key. Bob publishes the public key so that if anyone wants to send an encrypted message to him, they can use it.Y is an element in Z
p
∗, which has a multiplicative inverse in the group.When Alice wants to send a messageM to Bob, she needs to use Bob’s public key to encrypt the message. The following are the steps she takes:Encryption
(i)
Encode the messageM such that 1 ≤M≤p – 1.
(ii)
Select a random exponentk.
(iii)
ComputeC
1 =g
k and C
2 =M ·Y
k.The encrypted message sent to Bob is a pair (C
1, C
2).Once Bob receives the message, he uses his private key to decrypt it in the following way:Decryption
(i)
ComputeC
1
-
b =g
-bk
(ii)
ComputeM= C
1
-
b · C
2 =g
-bk ·M ·g
bk.The elementC
1
-
b is the multiplicative inverse ofg
bk.


## 2.1.1. Finite Field

Definition 1.
A finite fieldF is a finite set on which addition, subtraction, multiplication, and division are defined and the following axioms are satisfied.(1)
Associative: for alla,b, and c in F,a + (b +c) = (a +b) +c anda · (b ·c) = (a ·b) ·c.
(2)
Commutative: for alla andb∈
F,a +b =b +a anda ·b =b ·a.
(3)
Existence of identity: there exists elementse and e
′
∈
F, such thata +e =e +a =a and a
·
e
′ = e
′ ·a =a.
(4)
Existence of inverse: for every elementa ∈
F, there exists an element -a such thata + (-a) =e. Similarly for every elementa ∈
F, there exists an elementa
−1
∈
F such thata ·a
−1 = e
′.
(5)
Distributive: for alla,b, and c in F,a · (b+c) = (a ·b) + (a ·c).
Note that an element -a is called additive inverse and another element is called multiplicative inverse. An element e is an additive identity and an element e
′ is multiplicative identity. In this paper, we takee = 0 and e
′ = 1.Definition 2 (finite field of orderp).
Letp be a prime. The set of integers Z
p = {
0, 1, 2, …,p - 1
} with addition and multiplication performed modulo p is a finite field of order p and is denoted as F
p = Z
p.Proposition 3 (multiplicative inverse).
Letp be a prime. Elementa∈
Z
p,a ≠ 0 has a multiplicative inverseb =a
−1 such thata ·b ≡ 1 m
o
d
p.Definition 4 (group of units).
Letp be a prime. A group F
p
∗ is a set that contains nonzero elements and is called a group of units.


## 2.1.2. Polynomials over Finite Field

Definition 5 (polynomial overF
p).
LetF
p be a field. Any expression (1)
f
x
=
∑
i
=
0
t
a
i
x
i
a
_
i
_
∈
F
p
,where t is an arbitrary positive integer which is called a polynomial over F
p.Definition 6 (degree of polynomialf(x)).
Given a nonzero polynomialf
x
=
∑
i
=
0
t
a
i
x
i, where a
t ≠ 0, the number t is said to be the degree off(x) denoted as degf(x).Definition 7 (equal polynomials).
Letf
x
=
∑
i
=
0
t
a
i
x
i and f
′
x
=
∑
i
=
0
m
b
i
x
i, where a
t ≠ 0 and b
m ≠ 0 are two polynomials of degrees t andm, respectively. The two polynomials are equal and writef(x) = f
′(x), ift =m and a
i = b
i for alli = {
0, 1, 2, …, t
}.Definition 8 (roots of a polynomial).
An elementα∈
F is called a root off(x) iff(α) = 0.Proposition 9.
A polynomialf
x
=
∑
i
=
0
t
a
i
x
i, a
i
∈
F of degree t cannot have more than t roots in the field F.


## 2.1.3. Lagrange Interpolation

This is a method of reconstructing a polynomial from given known points. The polynomial constructed by Lagrange interpolation is called Lagrange interpolation polynomial, which is unique. To reconstruct the polynomial of degreet,t + 1 values are required, i.e., (α
i, β
i) for alli = 0, 1, 2, …,t such thatf(α
i) = β
i.Proposition 10.
Letα
ifor alli = 0, 1, 2, …,t be distinct elements ofF and β
ifor alli = 0, 1, 2, …,t be arbitrary elements ofF. There exists no more than one polynomialf(x) of degree at most t such that f(α
i) = β
i for alli = 0, 1, 2, …,t.Theorem 11 (see [33]).
Letα
0, α
1, …, α
t be distinct elements ofF and β
0, β
1, …, β
t be arbitrary elements ofF. There exists a unique polynomial(2)
f
x
=
∑
i
=
1
t
β
i
x
-
α
0
…
x
-
α
i
-
1
x
-
α
i
+
1
…
x
-
α
t
α
i
-
α
0
…
α
i
-
α
i
-
1
α
i
-
α
i
+
1
…
α
i
-
α
tof degree at most t such thatf(α
i) = β
ifor alli = 0, 1, 2, …,t.Proof.
We adopt the proof by Slinko [33]. The polynomial in Equation (2) was constructed as follows. First construct polynomials g
i(x) of degree t such that g
i(α
i) = 1 and g
i(α
j) = 0 fori ≠j. These polynomials are(3)
g
i
x
=
x
-
α
0
…
x
-
α
i
-
1
x
-
α
i
+
1
…
x
-
α
t
α
i
-
α
0
…
α
i
-
α
i
-
1
α
i
-
α
i
+
1
…
α
i
-
α
t
.Thus, the polynomials g
0(x), g
1(x), …, g
t(x) are constructed. Furthermore, we multiply by β
i fori = 0, 1, 2, …,t and obtain the polynomials β
0
g
0(x), β
1
g
1(x), …, β
t
g
t(x). Summing the polynomials β
i
g
i(x) the desired polynomialf(x) is constructed as Equation (4).(4)
f
x
=
∑
i
=
0
t
β
i
g
i
xWe setf(α
i) = β
i as required. This polynomial is unique by Proposition 10.


## 2.1.4. ElGamal Cryptosystem

ElGamal cryptosystem is in a family of public key cryptography [35]. Public key cryptography uses public key and private key to encrypt and decrypt messages, respectively, such that knowledge of private key makes decryption easy. Without knowing the private key, it is impossible to decrypt a message in acceptable time. Security of ElGamal is based on discrete logarithm problem (DLP). Therefore, an attacker has to solve DLP to decrypt an intercepted message on ElGamal cryptosystem.Definition 12 (finite field DLP (FFDLP)).
Given a finite fieldF
p, a primitive element g of F
p, and a nonzero element b of F
p, the FFDLP of b to baseg, written as logg(b), is determining the least nonnegative integer i such thatd =g
i.Three algorithms are used in ElGamal cryptosystem, which are key generation, encryption, and decryption. We assume Alice and Bob want to communicate over an insecure channel. They have to generate a public and private key pair for encryption and decryption as follows.Key Generation. Bob will do the following steps:(i)
Generate a large primep and a generator g of a multiplicative group Z
p
∗
(ii)
Select a random integerb ∈
Z
p
∗ such that 1 ≤b≤p – 2
(iii)
ComputeY ≡g
b modp.The public key for Bob is (p,g,Y) and b is the private key. Bob publishes the public key so that if anyone wants to send an encrypted message to him, they can use it.Y is an element in Z
p
∗, which has a multiplicative inverse in the group.When Alice wants to send a messageM to Bob, she needs to use Bob’s public key to encrypt the message. The following are the steps she takes:Encryption
(i)
Encode the messageM such that 1 ≤M≤p – 1.
(ii)
Select a random exponentk.
(iii)
ComputeC
1 =g
k and C
2 =M ·Y
k.The encrypted message sent to Bob is a pair (C
1, C
2).Once Bob receives the message, he uses his private key to decrypt it in the following way:Decryption
(i)
ComputeC
1
-
b =g
-bk
(ii)
ComputeM= C
1
-
b · C
2 =g
-bk ·M ·g
bk.The elementC
1
-
b is the multiplicative inverse ofg
bk.


## 2.2. Related Works

This section reviews linear secret sharing schemes, access structure of secret sharing schemes, and some previous schemes like Shamir’s and Liu et al.’s schemes [6, 14]. Furthermore, the section discusses the strong and weak properties of the reviewed schemes.


### 2.2.1. Linear Secret Sharing Scheme

Linear (t,n) secret sharing scheme is a special type of secret sharing scheme where all the n shares of the secret satisfy a linear relationship [6, 14]. The Definition 13 gives what linear secret sharing scheme is.Definition 13 (linear secret sharing scheme).
A (t,n) secret sharing scheme is a linear secret sharing scheme when the n shares, v
1, v
2, …, v
n can be presented as in Equation (5) (5)
v
1
,
v
2
,
…
,
v
n
=
k
1
,
k
2
,
…
,
k
t
H
,where H is a publict ×n matrix whose anyt ×t submatrix is not singular. The vector (k
1, k
2, …, k
t) is randomly chosen by the dealer.According to Definition13, we can see that Shamir’s (t,n) secret sharing scheme is a linear scheme. Let(6)
f
x
=
a
0
+
a
1
x
+
a
2
x
2
+
…
+
a
t
-
1
x
t
-
1
.The shares v
i =f(i),i = 1, 2, …,n can be presented as in Equation (7)(7)
v
1
,
v
2
,
…
,
v
n
=
a
0
,
a
1
,
a
2
,
…
,
a
t
-
1
H
,where h
i
,
j =j
i1 (h
i
,
j denotes the entry atith row andjth column of matrixH).


### 2.2.2. Access Structure

Assume thatU is the set of users whereU = {
U
1, U
2, …, U
n
} and D is the dealer who facilitates secret sharing. An access structure is defined as follows.Definition 14 (access structure).
Let 2U be the power set of the set of all users U. The set Γ ⊆ 2U of all authorized coalitions is called the access structure of the secret sharing scheme [33].
If a subset is in the access structure, all sets that contain that subset should also form part of the access structure. LetX and Y be subsets of Γ such thatX⊆ Y. An access structure Γ may be any subset of 2U such that (8)
X
∈
Γ
a
n
d
X
⊆
Y
,
t
h
e
n
Y
∈
Γ
.
The condition in Equation (8) attached to access structure is called monotone property, which shows that if a smaller subset can know the secret, then any other larger set containing the subset will know it too.Definition 15.
Let Γ⊆ 2U be an access structure. A coalitionC⊆ U is called minimal authorized coalition if it is authorized and any proper subset of C is not authorized [33].
For example, ifT⊂ C and C is the minimal authorized coalition, then T is not authorized because |
T
| < |
C
|. The assumption is that every user is in at least one minimal coalition and otherwise is not useful in reconstructing the secret. In a linear (t,n) secret sharing scheme, the minimal coalition has subsets with t users.


### 2.2.3. Shamir’s (t,n) Threshold Scheme

Shamir proposed a (t,n) threshold scheme that splits a secrets∈ S into n shares, which are distributed to n users [6]. Splitting is done by a dealer using an algorithm called share generation algorithm. The algorithm uses a polynomialf(x) of degreet - 1 to generate and distribute shares. The secret is reconstructed based on interpolating a polynomial using Lagrange interpolation, which is reconstructed by t users. The users combine their shares to reconstruct a polynomial f
′(x) of degree t using reconstruction algorithm. The algorithm inputs the user’s identity i and their share v
i, which forms a point or an ordered pair (i, v
i) for alli = 1, 2, …,t and outputs the secret f
′(0) =s. Shamir’s scheme has the following important properties.(i)
Share size is exactly equal to secret size.
(ii)
If a new player joins or leaves, it is easy to add or delete shares without affecting the other shares.
(iii)
It is easy to change the shares of the same secret just by changing the polynomial without breaching any security.
(iv)
t - 1 users do not reveal any information about the secret.However, Tompa and Woll discovered that the scheme cannot withstand cheating if there is an untrusted user during secret reconstruction [7]. As a result, Shamir’s scheme faces the following challenges during secret reconstruction.(i)
Any malicious user can present a forged share without being noticed.
(ii)
It is difficult to detect if the reconstructed secret is invalid.
(iii)
A malicious user, once is successful in cheating other users, will be able to reconstruct the valid secret.


### 2.2.4. Cheating Prevention

Cheating prevention in secret sharing became a great concern after Tompa and Woll introduced cheating concept. As a result, many schemes with cheating prevention are proposed where some detect cheating, others identify cheaters, and so on. Some of the categories of cheating prevention are as follows.(i)
Cheating detection: schemes provide the method to detect any forged share submitted for secret reconstruction by malicious user [7, 12]. The assumption is that the dealer is trusted.
(ii)
Cheater identification: schemes provide the method to detect and identify any forged share presented for secret reconstruction by a malicious user [15, 17]. The assumption is that the dealer is trusted.
(iii)
Robust secret sharing: schemes assume the dealer is trusted. Schemes can reconstruct a correct secret even if there are a number of forged shares presented by untrusted user [22].
(iv)
Verifiable secret sharing: schemes assume that the dealer is not trusted. Each user verifies the shares if valid using verification algorithm before reconstruction is done [9, 25].


### 2.2.5. Liu Et Al.’s Scheme

Liu et al. proposed a linear threshold secret sharing scheme, which is capable of cheating detection with share size|
v
i
| ≥ |
s
| / ε, where ε > 0 is the probability of cheating [14]. Liu et al.’s scheme is a combination of two Shamir’s schemes. Two polynomials are used to share a secret s. Cheating detection is done by finding a random elementr∈
Z
p during secret reconstruction.Liu et al.’s scheme adopts Shamir’s scheme in sharing the secret. This means that most properties of Liu et al.’s scheme are similar to Shamir’s scheme. However, there are some properties, which Shamir’s scheme does not have. The properties include the following.(i)
Share size given to each user is equal to or greater than the secret size, i.e.,|
v
i
| ≥ |
s
| / ε.
(ii)
Detect cheating whenever a forged share is presented during reconstruction.However, the scheme uses two polynomials to achieve the property of cheating detection, which makes number of computations to double as compared to Shamir’s scheme.


## 2.2.1. Linear Secret Sharing Scheme

Linear (t,n) secret sharing scheme is a special type of secret sharing scheme where all the n shares of the secret satisfy a linear relationship [6, 14]. The Definition 13 gives what linear secret sharing scheme is.Definition 13 (linear secret sharing scheme).
A (t,n) secret sharing scheme is a linear secret sharing scheme when the n shares, v
1, v
2, …, v
n can be presented as in Equation (5) (5)
v
1
,
v
2
,
…
,
v
n
=
k
1
,
k
2
,
…
,
k
t
H
,where H is a publict ×n matrix whose anyt ×t submatrix is not singular. The vector (k
1, k
2, …, k
t) is randomly chosen by the dealer.According to Definition13, we can see that Shamir’s (t,n) secret sharing scheme is a linear scheme. Let(6)
f
x
=
a
0
+
a
1
x
+
a
2
x
2
+
…
+
a
t
-
1
x
t
-
1
.The shares v
i =f(i),i = 1, 2, …,n can be presented as in Equation (7)(7)
v
1
,
v
2
,
…
,
v
n
=
a
0
,
a
1
,
a
2
,
…
,
a
t
-
1
H
,where h
i
,
j =j
i1 (h
i
,
j denotes the entry atith row andjth column of matrixH).


## 2.2.2. Access Structure

Assume thatU is the set of users whereU = {
U
1, U
2, …, U
n
} and D is the dealer who facilitates secret sharing. An access structure is defined as follows.Definition 14 (access structure).
Let 2U be the power set of the set of all users U. The set Γ ⊆ 2U of all authorized coalitions is called the access structure of the secret sharing scheme [33].
If a subset is in the access structure, all sets that contain that subset should also form part of the access structure. LetX and Y be subsets of Γ such thatX⊆ Y. An access structure Γ may be any subset of 2U such that (8)
X
∈
Γ
a
n
d
X
⊆
Y
,
t
h
e
n
Y
∈
Γ
.
The condition in Equation (8) attached to access structure is called monotone property, which shows that if a smaller subset can know the secret, then any other larger set containing the subset will know it too.Definition 15.
Let Γ⊆ 2U be an access structure. A coalitionC⊆ U is called minimal authorized coalition if it is authorized and any proper subset of C is not authorized [33].
For example, ifT⊂ C and C is the minimal authorized coalition, then T is not authorized because |
T
| < |
C
|. The assumption is that every user is in at least one minimal coalition and otherwise is not useful in reconstructing the secret. In a linear (t,n) secret sharing scheme, the minimal coalition has subsets with t users.


## 2.2.3. Shamir’s (t,n) Threshold Scheme

Shamir proposed a (t,n) threshold scheme that splits a secrets∈ S into n shares, which are distributed to n users [6]. Splitting is done by a dealer using an algorithm called share generation algorithm. The algorithm uses a polynomialf(x) of degreet - 1 to generate and distribute shares. The secret is reconstructed based on interpolating a polynomial using Lagrange interpolation, which is reconstructed by t users. The users combine their shares to reconstruct a polynomial f
′(x) of degree t using reconstruction algorithm. The algorithm inputs the user’s identity i and their share v
i, which forms a point or an ordered pair (i, v
i) for alli = 1, 2, …,t and outputs the secret f
′(0) =s. Shamir’s scheme has the following important properties.(i)
Share size is exactly equal to secret size.
(ii)
If a new player joins or leaves, it is easy to add or delete shares without affecting the other shares.
(iii)
It is easy to change the shares of the same secret just by changing the polynomial without breaching any security.
(iv)
t - 1 users do not reveal any information about the secret.However, Tompa and Woll discovered that the scheme cannot withstand cheating if there is an untrusted user during secret reconstruction [7]. As a result, Shamir’s scheme faces the following challenges during secret reconstruction.(i)
Any malicious user can present a forged share without being noticed.
(ii)
It is difficult to detect if the reconstructed secret is invalid.
(iii)
A malicious user, once is successful in cheating other users, will be able to reconstruct the valid secret.


## 2.2.4. Cheating Prevention

Cheating prevention in secret sharing became a great concern after Tompa and Woll introduced cheating concept. As a result, many schemes with cheating prevention are proposed where some detect cheating, others identify cheaters, and so on. Some of the categories of cheating prevention are as follows.(i)
Cheating detection: schemes provide the method to detect any forged share submitted for secret reconstruction by malicious user [7, 12]. The assumption is that the dealer is trusted.
(ii)
Cheater identification: schemes provide the method to detect and identify any forged share presented for secret reconstruction by a malicious user [15, 17]. The assumption is that the dealer is trusted.
(iii)
Robust secret sharing: schemes assume the dealer is trusted. Schemes can reconstruct a correct secret even if there are a number of forged shares presented by untrusted user [22].
(iv)
Verifiable secret sharing: schemes assume that the dealer is not trusted. Each user verifies the shares if valid using verification algorithm before reconstruction is done [9, 25].


## 2.2.5. Liu Et Al.’s Scheme

Liu et al. proposed a linear threshold secret sharing scheme, which is capable of cheating detection with share size|
v
i
| ≥ |
s
| / ε, where ε > 0 is the probability of cheating [14]. Liu et al.’s scheme is a combination of two Shamir’s schemes. Two polynomials are used to share a secret s. Cheating detection is done by finding a random elementr∈
Z
p during secret reconstruction.Liu et al.’s scheme adopts Shamir’s scheme in sharing the secret. This means that most properties of Liu et al.’s scheme are similar to Shamir’s scheme. However, there are some properties, which Shamir’s scheme does not have. The properties include the following.(i)
Share size given to each user is equal to or greater than the secret size, i.e.,|
v
i
| ≥ |
s
| / ε.
(ii)
Detect cheating whenever a forged share is presented during reconstruction.However, the scheme uses two polynomials to achieve the property of cheating detection, which makes number of computations to double as compared to Shamir’s scheme.


## 3. New Linear(
t
,
n
) Secret Sharing Scheme

This section proposes a new linear (t,n) threshold secret sharing scheme called polynomial based linear scheme (PBLS), which is based on one polynomial to reduce computational overhead of Liu et al.’s scheme and improve security of Shamir’s scheme in terms of cheating detection. PBLS is capable of cheating detection for any forged shares presented for secret reconstruction with the help of the coefficients of x in the polynomial f
′(x). The coefficients are determined by a basic scheme which is an initialization of PBLS that adopts its properties from ElGamal cryptosystem. The security of PBLS is based on Shamir’s scheme and ElGamal cryptosystem. PBLS provides perfect secret sharing, which is a required feature in all secret sharing schemes. The designed properties of PBLS withdrawn from the previous schemes satisfy SP1, SP2, SP3, and SP4, and computation overhead concern of CO.


### 3.1. Fundamental Properties

Basic scheme and PBLS adopt their properties from already existing scheme of ElGamal and Shamir. This makes the security of basic scheme and PBLS similar to the security of Shamir’s scheme and ElGamal cryptosystem.


#### 3.1.1. Properties of Basic Scheme

Basic scheme adopts its properties from ElGamal cryptosystem, which uses finite field elements to hide information [35]. The aim of basic scheme is to hide a secret in share generation phase but can be revealed when cheating detection is taking place. Secret hiding is done by multiplying a random element r by the secrets ∈ S to produce z for allr,s, andz∈
F
p. The secret is revealed when a multiplicative inverse of r is multiplied byz.Security of ElGamal cryptosystem depends on the hardness of FFDLP. Therefore, basic scheme adopts the same security as ElGamal cryptosystem. Propositions18 and 19 give the properties of basic scheme. However, to understand these properties better, we first provide Definition 16 and Corollary 17 without proof. The proofs for definition and corollary can be obtained in [36].Definition 16.
a ≡b mod p if and only if a and b leave the same remainder when divided byp.Corollary 17.
The integerc is the remainder when a is divided by p if and only ifa ≡c modp, where 0 ≤c <p.The following are the properties of basic scheme.Proposition 18.
Lets andr ∈
Z
p be a secret and a random element, respectively, andz ≡s·r mod p such that p is prime. It has FFDLP difficulty to withdraw s and r from the elementz∈
Z
p.Proof.
Since elementss and r are field elements, the operationn =s ·r ≡z mod p is a modulo multiplication. Thus z is a remainder when p divides the integer n. Assume that there exists only one integern, which leaves a remainder z when p
∣
n, then(9)
n
=
t
·
p
+
z
∀
t
>
0
.
By Corollary17,n ≡z mod p. Therefore,tis unique. Letd =a ·b such thata ≠s ≠r andb ≠s ≠r. By Definition 16,n ≡d mod p if and only if n and d leave the same remainder when they are divided by p. Thus(10)
n
=
t
·
p
+
z
d
=
t
·
p
+
z
∀
t
>
0
.
This implies that(11)
n
=
d
s
·
r
=
a
·
b
.
Buta ≠s ≠r andb ≠s ≠r. Therefore,t is not unique. This contradicts the fact that n is the only integer that leaves a remainder z when p
∣
n. Thereforen ≡d mod p, whered ≠n. Element z is a remainder whenevert·p divides d such thatd>t·p and n such thatn >t·p. Integers d and n contain different factors since they are not equal hence difficult to determine s and r fromz, which is FFDLP.Proposition 19.
Letz ≡s·r
m
o
d
p such thats∈
Z
p is a secret,r∈
Z
p is a random element, and p is prime. It is impossible to determine s fromz, which is based on the difficulty of the fractional decomposition.Proof.
By Proposition18, it is difficult to determine s and r from z because z does not reveal s and r. If we assume that we know the value ofr, then it is possible to determine s. Since r is known, the multiplicative inverse of r can be computed from finite field F
p. Multiplying z byr
−1 gives s as follows:(12)
z
·
r
-
1
≡
s
·
r
·
r
-
1
m
o
d
p
≡
s
m
o
d
p
.
Knowledge ofr helps to determine s. Therefore, by contrapositive, we cannot determine s fromz, which is based on the fractional decomposition difficulty.It is noted that though FFDLP is applied in basic scheme, there is a difference with ElGamal cryptosystem. The difference is that basic scheme makes no use of exponentiation, which helps it to operate in polynomial time.


#### 3.1.2. Properties of PBLS

Any secret sharing scheme should be secure from malicious users by denying them the opportunity to obtain the secret when the required number of users is not reached. At the same time, the secret should be able to be reconstructed after sharing. PBLS adopts its properties from Shamir’s secret sharing scheme, which shares a secret ton users to be recovered by t users wheret ≤nusing a polynomial of degreet – 1, where the coefficients of x
0 and x are s andz, respectively. Therefore, all the properties for Shamir’s scheme also hold for PBLS. However, PBLS also consists of some properties of ElGamal cryptosystem because of the use of basic scheme. Two fundamental properties of designing PBLS, which are adopted from Shamir’s scheme, are given in Proposition 20 such that every secret sharing scheme has to be achieved.Proposition 20 (SP1 and SP3).
Lets be the secret and t the threshold. Any less than t users cannot know the secret.Proposition 21 (SP2).
Lett be the threshold of a secret sharing scheme. Any t or more than t users should be able to reconstruct the secret by combining their shares together.Since Shamir’s scheme is linear that isn shares of secret satisfy a linear relationship, PBLS is also linear. However, PBLS has a property of SP4 as in Proposition 22.Proposition 22 (SP4).
Lett be the threshold of a secret sharing scheme and there are any less than t forged shares used for secret reconstruction. The shares will be detected during secret reconstruction.Any secret sharing scheme, which prevents cheating, must give to each participant shares whose sizes are at least the size of the secret plus log 1/ε, where ε is the probability of successful cheating [26]. The Proposition 23 gives a property of the share size of PBLS given to users.Proposition 23.
Letv
i = {
f(i), y
} be the share given to each user. The share size of PBLS attains the bounds of |
v
1
| ≥ |
s
|/ε.Any secret sharing scheme has a set of users who are allowed to make reconstruction of the secret called the access structure based on Definitions14 and 15. Proposition 24 provides an access structure of PBLS.Proposition 24.
LetU = {
U
1, U
2, …, U
n
} be the set of users. The access structure of PBLS is a set Γ ⊆
2
|
U
| such thatX⊆ Γ, where |
X
| ≥t.Proof.
The scheme uses Lagrange interpolation to come up with a polynomialf(x) of degreet - 1. By Theorem 11,t points are required to interpolate this polynomial. Thus any subset of t or more than t shares is authorized to reconstruct the secret.PBLS is composed of basic scheme and Shamir’s scheme. However, exponentiation is not used in PBLS to reduce computation cost. Figure1 shows the properties of ElGamal cryptosystem and Shamir’s secret sharing scheme and how they are adopted in basic scheme and PBLS.Figure 1
Adoption of ElGamal cryptosystem and Shamir’s scheme in PBLS.


#### 3.1.3. Adversary Model

In any cryptographic application, an attackerA has different goals to achieve for the attack mode to it. Secret sharing schemes face cheating attack, which was discovered by Tompa and Woll. Despite different applications of secret sharing schemes, a malicious user presents forged shares during secret reconstruction. Therefore, the following are some goals of cheaters in secret sharing schemes try to achieve:(i)
To recover the valid secret while the honest users are unable to detect cheating [29]. In this case, honest users believe the secret to be valid.
(ii)
To recover the secret while the honest users are able to detect cheating [37]. The honest users will not have access to this secret; hence, they simply assist A to reconstruct it without their knowledge.There are two assumptions in which cheaters behave. These are OKS and CDV as discussed [26, 27]. CDV assumes that cheaters already know the secret to be reconstructed. They only aim at blocking the correct reconstruction of the secret while they already have the secret. Honest users will get the invalid secret. On the other hand, OKS assumes that the cheater does not know the secret to be reconstructed. The aim is to block the correct reconstruction of the secret, but at the end they should be able to get a valid secret. PBLS considers OKS assumption because the aim of secret sharing is that the secret should not be known before reconstruction.Cheating becomes successful when cheaters managed to reconstruct a valid secret while honest users failed to detect that cheating takes place. PBLS makes sure thatA does not recover the secret whenever cheating detection is achieved. To prevent A from learning the secret, a closed reconstruction is done where no user can see the share of the other users. This also prevents malicious users who communicate their shares during reconstruction after learning the shares of honest user as described by [38]. Such users are called rushing cheaters.


### 3.2. Proposed Schemes

This subsection proposes basic scheme and PBLS. Basic scheme has two algorithms, which are secret hiding and secret revealing. The secret is hidden with field element in secret hiding algorithm. It is revealed using the multiplicative inverse of the element in secret revealing algorithm. PBLS has three algorithms, which are share generation, secret reconstruction, and cheating detection.


#### 3.2.1. Basic Scheme

This subsection proposes basic scheme, which is the basis for constructing PBLS proposed in Section3.2.2. Basic scheme provides a conceptual process of how PBLS detects cheating during secret reconstruction. A secret is hidden by a field element r and can be revealed by a multiplicative inverse b of the elementr.Secret Hiding. Consider a finite field F
p in which p is a prime such thatp - 1 has at least one large prime factor. Ifp - 1 has only small prime factors, then computing FFDLP is easy as pointed out by [5]. By Proposition 3, all nonzero elements a in F
p have a multiplicative inverse b such thata·b ≡ 1 mod p. A secret s is also the field element ass∈
F
p. Any random number r except 1 can be used to hide the secret s. The algorithm for hiding the secret avoids using 1 because it is a multiplicative identity therefore cannot hide s. After multiplying r bys, a different field element z is obtained. Hence Equation (13) follows(13)
z
≡
r
·
s
m
o
d
p
.Algorithm25 describes how a secret s is hidden using field element in basic scheme.Algorithm 25 (secret hiding).
Input. Secrets
Output. Elementz
Process
(i)
Choose a random elementr∈
Z
p.
(ii)
Computez by multiplying r bys.
(iii)
Output elementz∈
Z
p.
Figure2 illustrates how Algorithm 25 works.
The elementz does not reveal any information of s and r in basic scheme.Figure 2
Secret hiding in basic scheme.Secret Revealing. Whenever one wants the secret s back, he (or she) simply computes the multiplicative inverse ofr, given as b, and multiplies it by z to get the secret s. Therefore, multiplying z by multiplicative inverse of r is the same as multiplying r byr
−1 by s. This means 1 is multiplied by s to get a result s as in Equation (14)(14)
s
≡
b
·
z
m
o
d
p
≡
r
-
1
·
r
·
s
m
o
d
p
≡
s
m
o
d
p
.Algorithm26 shows how to reveal the secret s using the multiplicative inverse ofr.Algorithm 26 (secret revealing).
Input. Elements z andr
Output. Secrets
Process
(i)
Compute multiplicative inverseb of elementr, i.e.,b=r
−1.
(ii)
Computes by multiplying b byz.
(iii)
Outputs.
Figure3 illustrates Algorithm 26: how revealing the secret occurs.Figure 3
Secret revealing in basic scheme.Basic scheme requiresr to be kept secret so that the secret remains private and secure. Otherwise, any adversary will be able to compute the inverse of r and reveal s as is done in Algorithm 26. We demonstrate this with a dummy example below.Example 27.
Letp = 23 ands = 12. Secret s can be hidden as follows. Choose a random elementr = 7 ∈
Z
23. Compute z by multiplying r by s to obtainz
(15)
z
≡
r
·
s
m
o
d
23
≡
7
·
12
m
o
d
23
≡
15
m
o
d
23
.
The secret 12 is hidden as 15. It is difficult for an adversaryA to know the secret 12 and the random 7 from 15 alone unless he (or she) solves FFDLP. The secret s is revealed by computingb, the multiplicative inverse ofr
(16)
b
=
r
-
1
=
10
,and computing s by multiplying y byz
(17)
s
≡
b
·
z
m
o
d
23
≡
10
·
15
m
o
d
23
≡
12
m
o
d
23
.
Note that in practice,p should be a large prime number for the scheme to be secure enough.


#### 3.2.2. Polynomial Based Linear Scheme (PBLS)

In this subsection, a linear (t,n) threshold secret sharing scheme, PBLS, is proposed, which provides cheating detection based on basic scheme and Shamir’s secret sharing. We assume using two trusted third parties dealer D and combinerC.D generates and distributes shares to n users while C collects any t shares and reconstructs the secret. A trusted user can also be C depending on the application.C does not reveal shares after reconstruction and hence performs a closed reconstruction. In addition,C performs cheating detection in secret reconstruction phase. PBLS has three algorithms, which are share generation, secret reconstruction, and cheating detection.Share Generation. As Shamir’s scheme, share generation algorithm starts with D setting public parameters, prime p and thresholdt.D chooses a random element r from a finite field F
p, then hides the secret using Algorithm 25. The output is elementz∈
F
p.D computesb∈
F
p, a multiplicative inverse of r. The element b is sent to n users on public channel while element z becomes a coefficient of x in polynomialf(x). To share the secrets,D chooses a random polynomial of degreet - 1, which has constraints of two coefficients, a
0 =s and a
1 =z.D computesf(i) for alli = 1, 2, …,n and distributes v
i = (i,f(i)) to users wherei = 1, 2, …,n. Algorithm 28 shows how shares are generated and distributed to users.Algorithm 28 (share generation).
Input. Secrets
Output. Secret shares v
i wherei = 1, 2, …,n
Process
(i)
D uses Algorithm 25 to computez.
(ii)
D uses Algorithm 26 to computeb.
(iii)
D chooses a random polynomialf(x) of degreet - 1 over F
p, i.e.,(18)
f
x
=
a
0
+
a
1
x
+
a
2
x
2
+
…
+
a
t
-
1
x
t
-
1
such thata
0 =s and a
1 =z.
(iv)
D computesf(i) and distributes v
i = (i,f(i)) and b to U
i for alli = 1, 2, …,n secretly.
Figure4 illustrates the share generation algorithm in PBLS.
Users cannot obtain information of the secrets from z without the knowledge of r unless they have to solve FFDLP.Figure 4
Share generation in PBLS.Secret Reconstruction. If the secret is required for use, anyt ≤n users combine their shares together to reconstruct it. The combiner can be one of the user or a trusted third party who does the reconstruction without revealing the shares. Users send their shares to C together withb.C uses Lagrange interpolation to reconstruct the polynomial of degreet - 1 from at least t points, i.e., (1,f(1)), (2,f(2)), … (i,f(i)) and the secret isf(0) if all users are honest. Figure 5 illustrates how secret reconstruction is done in PBLS.Figure 5
Secret reconstruction in PBLS.Algorithm 29 (secret reconstruction).
Input. Any list of t shares
Output. Secret s
′ =s if there is no cheater or s
′ ≠s if cheaters exist
Process
(i)
C reconstructs f
′(x) from (i, v
i) using Lagrange interpolation (19)
f
′
x
=
∑
i
=
1
t
v
i
∏
j
=
1
,
j
≠
i
t
x
i
-
x
x
i
-
x
j
(ii)
C outputs polynomial f
′(x) = a
0
′ + a
1
′
x + a
2
′
x
2 + … + a
t
-
1
′
x
t-1.
By Theorem11, the reconstructed polynomial f
′(x) is unique and if there is no cheating then polynomial f
′(x) is equal to polynomialf(x). Therefore, the secret is f
′(0) = a
0
′ = s
′ =s.Cheating Detection. It is important to check if there are forged shares presented during secret reconstruction. In this phase, PBLS uses basic scheme to reveal the secret since it is hidden in the coefficient of x of the polynomialf(x). Consequently, the polynomial f
′(x) should have the same coefficient. The secret is revealed by multiplying the coefficient of x by a multiplicative inverse of an element r. If the result gives term a
0
′, then there is no cheating. Therefore, the secret is valid. Otherwise, some forged shares are used during reconstruction of the secret. Algorithm 30 shows how cheating detection is done.Algorithm 30 (cheating detection).
Input. Elements z andb
Output. No cheating or cheating
Process
(i)
C computesb·z = a
0
′.
(ii)
C outputs no cheating if a
0
′ holds or cheating otherwise.
C uses Algorithm 30 to detect if forged shares were presented to reconstruct the secret.C uses multiply a
1
′ by b to get a
0
′. Once the output is not a
0
′, then cheating took place, secret reconstruction halted, and the reconstructed secret was not valid.C sends to users a signal that secret reconstruction has failed. In cases where all users are honest, Algorithm 30 outputs no cheating. Consequently, the output Algorithm 29 valid and C sends a
0
′ to each user, which shows that secret reconstruct is successful. A simple example below demonstrates how the new scheme works.Example 31.
Letp = 23. Given the secrets = 12, we can share it ton= 6 users such that anyt = 4 of them can reconstruct the secret.
We use Algorithm25 to hide the secret and select a randomr ∈
F
23 as 15(20)
z
≡
s
·
r
m
o
d
p
≡
12
·
15
m
o
d
23
≡
19
.
We also compute a multiplicative inverse ofr.(21)
b
≡
r
-
1
m
o
d
p
≡
15
-
1
m
o
d
23
≡
20
m
o
d
23
.
Let the random polynomial be(22)
f
x
=
12
+
19
x
+
20
x
2
+
9
x
3
.
The shares given to users are(23)
U
1
:
f
1
=
12
+
19
×
1
+
20
×
1
2
+
9
×
1
3
=
14
U
2
:
f
2
=
12
+
19
×
2
+
20
×
2
2
+
9
×
2
3
=
18
U
3
:
f
3
=
12
+
19
×
3
+
20
×
3
2
+
9
×
3
3
=
9
U
4
:
f
4
=
12
+
19
×
4
+
20
×
4
2
+
9
×
4
3
=
18
U
5
:
f
5
=
12
+
19
×
5
+
20
×
5
2
+
9
×
5
3
=
7
U
6
:
f
6
=
12
+
19
×
6
+
20
×
6
2
+
9
×
6
3
=
7
.
Each user also receives 20 a multiplicative inverse of 15∈
F
23.
When the secret is required, any 4 users send their shares toC to reconstruct the secret s. Let U
1, U
3, U
5, and U
6 send their shares to C. We use Lagrange interpolation to reconstruct a polynomial f
′(x). We find the g
i(x) ∀i = {
0, 1, 2, 3
} as discussed in Section 2.1.3
(24)
g
0
x
=
x
-
3
x
-
5
x
-
6
1
-
3
1
-
5
1
-
6
=
4
x
3
+
9
x
2
+
17
x
+
2
=
4
x
3
+
13
x
2
+
22
x
+
8
g
1
x
=
x
-
1
x
-
5
x
-
6
3
-
1
3
-
5
3
-
6
=
2
x
3
+
11
x
2
+
18
x
+
16
=
2
x
3
+
22
x
2
+
13
x
+
9
g
2
x
=
x
-
1
x
-
3
x
-
6
5
-
1
5
-
3
5
-
6
=
20
x
3
+
13
x
2
+
4
x
+
5
=
20
x
3
+
7
x
2
+
11
x
+
8
g
3
x
=
x
-
1
x
-
3
x
-
5
6
-
1
6
-
3
6
-
5
=
20
x
3
+
14
x
2
+
8
=
20
x
3
+
4
x
2
+
22
.
Therefore, the polynomialf
′(x) is(25)
f
′
x
=
f
1
g
0
x
+
f
3
g
1
x
+
f
5
g
2
x
+
f
6
g
3
x
=
14
4
x
3
+
13
x
2
+
22
x
+
8
+
9
2
x
3
+
22
x
2
+
13
x
+
9
+
7
20
x
3
+
7
x
2
+
11
x
+
8
+
7
20
x
3
+
4
x
2
+
22
=
9
x
3
+
20
x
2
+
19
x
+
12
The polynomialf
′(x) = 9x
3 + 20x
2 + 19x +12 is the same used to share the secret. Cheating detection is done by multiplying 19 by 20, which gives 12. Assuming users U
1, U
3, and U
5 want to cheat U
6. Let the forged shares be U
1: (1, 8), U
3: (3, 10), U
5: (5, 17) and U
6: (6, 7).C reconstructs a polynomial(26)
f
′
x
=
3
x
3
+
11
x
2
+
10
x
+
7
.
Multiplying 11 by 20 gives 12, which is not equal to 7. Cheating is detected by cheating detection algorithm in PBLS.


## 3.1. Fundamental Properties

Basic scheme and PBLS adopt their properties from already existing scheme of ElGamal and Shamir. This makes the security of basic scheme and PBLS similar to the security of Shamir’s scheme and ElGamal cryptosystem.


### 3.1.1. Properties of Basic Scheme

Basic scheme adopts its properties from ElGamal cryptosystem, which uses finite field elements to hide information [35]. The aim of basic scheme is to hide a secret in share generation phase but can be revealed when cheating detection is taking place. Secret hiding is done by multiplying a random element r by the secrets ∈ S to produce z for allr,s, andz∈
F
p. The secret is revealed when a multiplicative inverse of r is multiplied byz.Security of ElGamal cryptosystem depends on the hardness of FFDLP. Therefore, basic scheme adopts the same security as ElGamal cryptosystem. Propositions18 and 19 give the properties of basic scheme. However, to understand these properties better, we first provide Definition 16 and Corollary 17 without proof. The proofs for definition and corollary can be obtained in [36].Definition 16.
a ≡b mod p if and only if a and b leave the same remainder when divided byp.Corollary 17.
The integerc is the remainder when a is divided by p if and only ifa ≡c modp, where 0 ≤c <p.The following are the properties of basic scheme.Proposition 18.
Lets andr ∈
Z
p be a secret and a random element, respectively, andz ≡s·r mod p such that p is prime. It has FFDLP difficulty to withdraw s and r from the elementz∈
Z
p.Proof.
Since elementss and r are field elements, the operationn =s ·r ≡z mod p is a modulo multiplication. Thus z is a remainder when p divides the integer n. Assume that there exists only one integern, which leaves a remainder z when p
∣
n, then(9)
n
=
t
·
p
+
z
∀
t
>
0
.
By Corollary17,n ≡z mod p. Therefore,tis unique. Letd =a ·b such thata ≠s ≠r andb ≠s ≠r. By Definition 16,n ≡d mod p if and only if n and d leave the same remainder when they are divided by p. Thus(10)
n
=
t
·
p
+
z
d
=
t
·
p
+
z
∀
t
>
0
.
This implies that(11)
n
=
d
s
·
r
=
a
·
b
.
Buta ≠s ≠r andb ≠s ≠r. Therefore,t is not unique. This contradicts the fact that n is the only integer that leaves a remainder z when p
∣
n. Thereforen ≡d mod p, whered ≠n. Element z is a remainder whenevert·p divides d such thatd>t·p and n such thatn >t·p. Integers d and n contain different factors since they are not equal hence difficult to determine s and r fromz, which is FFDLP.Proposition 19.
Letz ≡s·r
m
o
d
p such thats∈
Z
p is a secret,r∈
Z
p is a random element, and p is prime. It is impossible to determine s fromz, which is based on the difficulty of the fractional decomposition.Proof.
By Proposition18, it is difficult to determine s and r from z because z does not reveal s and r. If we assume that we know the value ofr, then it is possible to determine s. Since r is known, the multiplicative inverse of r can be computed from finite field F
p. Multiplying z byr
−1 gives s as follows:(12)
z
·
r
-
1
≡
s
·
r
·
r
-
1
m
o
d
p
≡
s
m
o
d
p
.
Knowledge ofr helps to determine s. Therefore, by contrapositive, we cannot determine s fromz, which is based on the fractional decomposition difficulty.It is noted that though FFDLP is applied in basic scheme, there is a difference with ElGamal cryptosystem. The difference is that basic scheme makes no use of exponentiation, which helps it to operate in polynomial time.


### 3.1.2. Properties of PBLS

Any secret sharing scheme should be secure from malicious users by denying them the opportunity to obtain the secret when the required number of users is not reached. At the same time, the secret should be able to be reconstructed after sharing. PBLS adopts its properties from Shamir’s secret sharing scheme, which shares a secret ton users to be recovered by t users wheret ≤nusing a polynomial of degreet – 1, where the coefficients of x
0 and x are s andz, respectively. Therefore, all the properties for Shamir’s scheme also hold for PBLS. However, PBLS also consists of some properties of ElGamal cryptosystem because of the use of basic scheme. Two fundamental properties of designing PBLS, which are adopted from Shamir’s scheme, are given in Proposition 20 such that every secret sharing scheme has to be achieved.Proposition 20 (SP1 and SP3).
Lets be the secret and t the threshold. Any less than t users cannot know the secret.Proposition 21 (SP2).
Lett be the threshold of a secret sharing scheme. Any t or more than t users should be able to reconstruct the secret by combining their shares together.Since Shamir’s scheme is linear that isn shares of secret satisfy a linear relationship, PBLS is also linear. However, PBLS has a property of SP4 as in Proposition 22.Proposition 22 (SP4).
Lett be the threshold of a secret sharing scheme and there are any less than t forged shares used for secret reconstruction. The shares will be detected during secret reconstruction.Any secret sharing scheme, which prevents cheating, must give to each participant shares whose sizes are at least the size of the secret plus log 1/ε, where ε is the probability of successful cheating [26]. The Proposition 23 gives a property of the share size of PBLS given to users.Proposition 23.
Letv
i = {
f(i), y
} be the share given to each user. The share size of PBLS attains the bounds of |
v
1
| ≥ |
s
|/ε.Any secret sharing scheme has a set of users who are allowed to make reconstruction of the secret called the access structure based on Definitions14 and 15. Proposition 24 provides an access structure of PBLS.Proposition 24.
LetU = {
U
1, U
2, …, U
n
} be the set of users. The access structure of PBLS is a set Γ ⊆
2
|
U
| such thatX⊆ Γ, where |
X
| ≥t.Proof.
The scheme uses Lagrange interpolation to come up with a polynomialf(x) of degreet - 1. By Theorem 11,t points are required to interpolate this polynomial. Thus any subset of t or more than t shares is authorized to reconstruct the secret.PBLS is composed of basic scheme and Shamir’s scheme. However, exponentiation is not used in PBLS to reduce computation cost. Figure1 shows the properties of ElGamal cryptosystem and Shamir’s secret sharing scheme and how they are adopted in basic scheme and PBLS.Figure 1
Adoption of ElGamal cryptosystem and Shamir’s scheme in PBLS.


### 3.1.3. Adversary Model

In any cryptographic application, an attackerA has different goals to achieve for the attack mode to it. Secret sharing schemes face cheating attack, which was discovered by Tompa and Woll. Despite different applications of secret sharing schemes, a malicious user presents forged shares during secret reconstruction. Therefore, the following are some goals of cheaters in secret sharing schemes try to achieve:(i)
To recover the valid secret while the honest users are unable to detect cheating [29]. In this case, honest users believe the secret to be valid.
(ii)
To recover the secret while the honest users are able to detect cheating [37]. The honest users will not have access to this secret; hence, they simply assist A to reconstruct it without their knowledge.There are two assumptions in which cheaters behave. These are OKS and CDV as discussed [26, 27]. CDV assumes that cheaters already know the secret to be reconstructed. They only aim at blocking the correct reconstruction of the secret while they already have the secret. Honest users will get the invalid secret. On the other hand, OKS assumes that the cheater does not know the secret to be reconstructed. The aim is to block the correct reconstruction of the secret, but at the end they should be able to get a valid secret. PBLS considers OKS assumption because the aim of secret sharing is that the secret should not be known before reconstruction.Cheating becomes successful when cheaters managed to reconstruct a valid secret while honest users failed to detect that cheating takes place. PBLS makes sure thatA does not recover the secret whenever cheating detection is achieved. To prevent A from learning the secret, a closed reconstruction is done where no user can see the share of the other users. This also prevents malicious users who communicate their shares during reconstruction after learning the shares of honest user as described by [38]. Such users are called rushing cheaters.


## 3.1.1. Properties of Basic Scheme

Basic scheme adopts its properties from ElGamal cryptosystem, which uses finite field elements to hide information [35]. The aim of basic scheme is to hide a secret in share generation phase but can be revealed when cheating detection is taking place. Secret hiding is done by multiplying a random element r by the secrets ∈ S to produce z for allr,s, andz∈
F
p. The secret is revealed when a multiplicative inverse of r is multiplied byz.Security of ElGamal cryptosystem depends on the hardness of FFDLP. Therefore, basic scheme adopts the same security as ElGamal cryptosystem. Propositions18 and 19 give the properties of basic scheme. However, to understand these properties better, we first provide Definition 16 and Corollary 17 without proof. The proofs for definition and corollary can be obtained in [36].Definition 16.
a ≡b mod p if and only if a and b leave the same remainder when divided byp.Corollary 17.
The integerc is the remainder when a is divided by p if and only ifa ≡c modp, where 0 ≤c <p.The following are the properties of basic scheme.Proposition 18.
Lets andr ∈
Z
p be a secret and a random element, respectively, andz ≡s·r mod p such that p is prime. It has FFDLP difficulty to withdraw s and r from the elementz∈
Z
p.Proof.
Since elementss and r are field elements, the operationn =s ·r ≡z mod p is a modulo multiplication. Thus z is a remainder when p divides the integer n. Assume that there exists only one integern, which leaves a remainder z when p
∣
n, then(9)
n
=
t
·
p
+
z
∀
t
>
0
.
By Corollary17,n ≡z mod p. Therefore,tis unique. Letd =a ·b such thata ≠s ≠r andb ≠s ≠r. By Definition 16,n ≡d mod p if and only if n and d leave the same remainder when they are divided by p. Thus(10)
n
=
t
·
p
+
z
d
=
t
·
p
+
z
∀
t
>
0
.
This implies that(11)
n
=
d
s
·
r
=
a
·
b
.
Buta ≠s ≠r andb ≠s ≠r. Therefore,t is not unique. This contradicts the fact that n is the only integer that leaves a remainder z when p
∣
n. Thereforen ≡d mod p, whered ≠n. Element z is a remainder whenevert·p divides d such thatd>t·p and n such thatn >t·p. Integers d and n contain different factors since they are not equal hence difficult to determine s and r fromz, which is FFDLP.Proposition 19.
Letz ≡s·r
m
o
d
p such thats∈
Z
p is a secret,r∈
Z
p is a random element, and p is prime. It is impossible to determine s fromz, which is based on the difficulty of the fractional decomposition.Proof.
By Proposition18, it is difficult to determine s and r from z because z does not reveal s and r. If we assume that we know the value ofr, then it is possible to determine s. Since r is known, the multiplicative inverse of r can be computed from finite field F
p. Multiplying z byr
−1 gives s as follows:(12)
z
·
r
-
1
≡
s
·
r
·
r
-
1
m
o
d
p
≡
s
m
o
d
p
.
Knowledge ofr helps to determine s. Therefore, by contrapositive, we cannot determine s fromz, which is based on the fractional decomposition difficulty.It is noted that though FFDLP is applied in basic scheme, there is a difference with ElGamal cryptosystem. The difference is that basic scheme makes no use of exponentiation, which helps it to operate in polynomial time.


## 3.1.2. Properties of PBLS

Any secret sharing scheme should be secure from malicious users by denying them the opportunity to obtain the secret when the required number of users is not reached. At the same time, the secret should be able to be reconstructed after sharing. PBLS adopts its properties from Shamir’s secret sharing scheme, which shares a secret ton users to be recovered by t users wheret ≤nusing a polynomial of degreet – 1, where the coefficients of x
0 and x are s andz, respectively. Therefore, all the properties for Shamir’s scheme also hold for PBLS. However, PBLS also consists of some properties of ElGamal cryptosystem because of the use of basic scheme. Two fundamental properties of designing PBLS, which are adopted from Shamir’s scheme, are given in Proposition 20 such that every secret sharing scheme has to be achieved.Proposition 20 (SP1 and SP3).
Lets be the secret and t the threshold. Any less than t users cannot know the secret.Proposition 21 (SP2).
Lett be the threshold of a secret sharing scheme. Any t or more than t users should be able to reconstruct the secret by combining their shares together.Since Shamir’s scheme is linear that isn shares of secret satisfy a linear relationship, PBLS is also linear. However, PBLS has a property of SP4 as in Proposition 22.Proposition 22 (SP4).
Lett be the threshold of a secret sharing scheme and there are any less than t forged shares used for secret reconstruction. The shares will be detected during secret reconstruction.Any secret sharing scheme, which prevents cheating, must give to each participant shares whose sizes are at least the size of the secret plus log 1/ε, where ε is the probability of successful cheating [26]. The Proposition 23 gives a property of the share size of PBLS given to users.Proposition 23.
Letv
i = {
f(i), y
} be the share given to each user. The share size of PBLS attains the bounds of |
v
1
| ≥ |
s
|/ε.Any secret sharing scheme has a set of users who are allowed to make reconstruction of the secret called the access structure based on Definitions14 and 15. Proposition 24 provides an access structure of PBLS.Proposition 24.
LetU = {
U
1, U
2, …, U
n
} be the set of users. The access structure of PBLS is a set Γ ⊆
2
|
U
| such thatX⊆ Γ, where |
X
| ≥t.Proof.
The scheme uses Lagrange interpolation to come up with a polynomialf(x) of degreet - 1. By Theorem 11,t points are required to interpolate this polynomial. Thus any subset of t or more than t shares is authorized to reconstruct the secret.PBLS is composed of basic scheme and Shamir’s scheme. However, exponentiation is not used in PBLS to reduce computation cost. Figure1 shows the properties of ElGamal cryptosystem and Shamir’s secret sharing scheme and how they are adopted in basic scheme and PBLS.Figure 1
Adoption of ElGamal cryptosystem and Shamir’s scheme in PBLS.


## 3.1.3. Adversary Model

In any cryptographic application, an attackerA has different goals to achieve for the attack mode to it. Secret sharing schemes face cheating attack, which was discovered by Tompa and Woll. Despite different applications of secret sharing schemes, a malicious user presents forged shares during secret reconstruction. Therefore, the following are some goals of cheaters in secret sharing schemes try to achieve:(i)
To recover the valid secret while the honest users are unable to detect cheating [29]. In this case, honest users believe the secret to be valid.
(ii)
To recover the secret while the honest users are able to detect cheating [37]. The honest users will not have access to this secret; hence, they simply assist A to reconstruct it without their knowledge.There are two assumptions in which cheaters behave. These are OKS and CDV as discussed [26, 27]. CDV assumes that cheaters already know the secret to be reconstructed. They only aim at blocking the correct reconstruction of the secret while they already have the secret. Honest users will get the invalid secret. On the other hand, OKS assumes that the cheater does not know the secret to be reconstructed. The aim is to block the correct reconstruction of the secret, but at the end they should be able to get a valid secret. PBLS considers OKS assumption because the aim of secret sharing is that the secret should not be known before reconstruction.Cheating becomes successful when cheaters managed to reconstruct a valid secret while honest users failed to detect that cheating takes place. PBLS makes sure thatA does not recover the secret whenever cheating detection is achieved. To prevent A from learning the secret, a closed reconstruction is done where no user can see the share of the other users. This also prevents malicious users who communicate their shares during reconstruction after learning the shares of honest user as described by [38]. Such users are called rushing cheaters.


## 3.2. Proposed Schemes

This subsection proposes basic scheme and PBLS. Basic scheme has two algorithms, which are secret hiding and secret revealing. The secret is hidden with field element in secret hiding algorithm. It is revealed using the multiplicative inverse of the element in secret revealing algorithm. PBLS has three algorithms, which are share generation, secret reconstruction, and cheating detection.


### 3.2.1. Basic Scheme

This subsection proposes basic scheme, which is the basis for constructing PBLS proposed in Section3.2.2. Basic scheme provides a conceptual process of how PBLS detects cheating during secret reconstruction. A secret is hidden by a field element r and can be revealed by a multiplicative inverse b of the elementr.Secret Hiding. Consider a finite field F
p in which p is a prime such thatp - 1 has at least one large prime factor. Ifp - 1 has only small prime factors, then computing FFDLP is easy as pointed out by [5]. By Proposition 3, all nonzero elements a in F
p have a multiplicative inverse b such thata·b ≡ 1 mod p. A secret s is also the field element ass∈
F
p. Any random number r except 1 can be used to hide the secret s. The algorithm for hiding the secret avoids using 1 because it is a multiplicative identity therefore cannot hide s. After multiplying r bys, a different field element z is obtained. Hence Equation (13) follows(13)
z
≡
r
·
s
m
o
d
p
.Algorithm25 describes how a secret s is hidden using field element in basic scheme.Algorithm 25 (secret hiding).
Input. Secrets
Output. Elementz
Process
(i)
Choose a random elementr∈
Z
p.
(ii)
Computez by multiplying r bys.
(iii)
Output elementz∈
Z
p.
Figure2 illustrates how Algorithm 25 works.
The elementz does not reveal any information of s and r in basic scheme.Figure 2
Secret hiding in basic scheme.Secret Revealing. Whenever one wants the secret s back, he (or she) simply computes the multiplicative inverse ofr, given as b, and multiplies it by z to get the secret s. Therefore, multiplying z by multiplicative inverse of r is the same as multiplying r byr
−1 by s. This means 1 is multiplied by s to get a result s as in Equation (14)(14)
s
≡
b
·
z
m
o
d
p
≡
r
-
1
·
r
·
s
m
o
d
p
≡
s
m
o
d
p
.Algorithm26 shows how to reveal the secret s using the multiplicative inverse ofr.Algorithm 26 (secret revealing).
Input. Elements z andr
Output. Secrets
Process
(i)
Compute multiplicative inverseb of elementr, i.e.,b=r
−1.
(ii)
Computes by multiplying b byz.
(iii)
Outputs.
Figure3 illustrates Algorithm 26: how revealing the secret occurs.Figure 3
Secret revealing in basic scheme.Basic scheme requiresr to be kept secret so that the secret remains private and secure. Otherwise, any adversary will be able to compute the inverse of r and reveal s as is done in Algorithm 26. We demonstrate this with a dummy example below.Example 27.
Letp = 23 ands = 12. Secret s can be hidden as follows. Choose a random elementr = 7 ∈
Z
23. Compute z by multiplying r by s to obtainz
(15)
z
≡
r
·
s
m
o
d
23
≡
7
·
12
m
o
d
23
≡
15
m
o
d
23
.
The secret 12 is hidden as 15. It is difficult for an adversaryA to know the secret 12 and the random 7 from 15 alone unless he (or she) solves FFDLP. The secret s is revealed by computingb, the multiplicative inverse ofr
(16)
b
=
r
-
1
=
10
,and computing s by multiplying y byz
(17)
s
≡
b
·
z
m
o
d
23
≡
10
·
15
m
o
d
23
≡
12
m
o
d
23
.
Note that in practice,p should be a large prime number for the scheme to be secure enough.


### 3.2.2. Polynomial Based Linear Scheme (PBLS)

In this subsection, a linear (t,n) threshold secret sharing scheme, PBLS, is proposed, which provides cheating detection based on basic scheme and Shamir’s secret sharing. We assume using two trusted third parties dealer D and combinerC.D generates and distributes shares to n users while C collects any t shares and reconstructs the secret. A trusted user can also be C depending on the application.C does not reveal shares after reconstruction and hence performs a closed reconstruction. In addition,C performs cheating detection in secret reconstruction phase. PBLS has three algorithms, which are share generation, secret reconstruction, and cheating detection.Share Generation. As Shamir’s scheme, share generation algorithm starts with D setting public parameters, prime p and thresholdt.D chooses a random element r from a finite field F
p, then hides the secret using Algorithm 25. The output is elementz∈
F
p.D computesb∈
F
p, a multiplicative inverse of r. The element b is sent to n users on public channel while element z becomes a coefficient of x in polynomialf(x). To share the secrets,D chooses a random polynomial of degreet - 1, which has constraints of two coefficients, a
0 =s and a
1 =z.D computesf(i) for alli = 1, 2, …,n and distributes v
i = (i,f(i)) to users wherei = 1, 2, …,n. Algorithm 28 shows how shares are generated and distributed to users.Algorithm 28 (share generation).
Input. Secrets
Output. Secret shares v
i wherei = 1, 2, …,n
Process
(i)
D uses Algorithm 25 to computez.
(ii)
D uses Algorithm 26 to computeb.
(iii)
D chooses a random polynomialf(x) of degreet - 1 over F
p, i.e.,(18)
f
x
=
a
0
+
a
1
x
+
a
2
x
2
+
…
+
a
t
-
1
x
t
-
1
such thata
0 =s and a
1 =z.
(iv)
D computesf(i) and distributes v
i = (i,f(i)) and b to U
i for alli = 1, 2, …,n secretly.
Figure4 illustrates the share generation algorithm in PBLS.
Users cannot obtain information of the secrets from z without the knowledge of r unless they have to solve FFDLP.Figure 4
Share generation in PBLS.Secret Reconstruction. If the secret is required for use, anyt ≤n users combine their shares together to reconstruct it. The combiner can be one of the user or a trusted third party who does the reconstruction without revealing the shares. Users send their shares to C together withb.C uses Lagrange interpolation to reconstruct the polynomial of degreet - 1 from at least t points, i.e., (1,f(1)), (2,f(2)), … (i,f(i)) and the secret isf(0) if all users are honest. Figure 5 illustrates how secret reconstruction is done in PBLS.Figure 5
Secret reconstruction in PBLS.Algorithm 29 (secret reconstruction).
Input. Any list of t shares
Output. Secret s
′ =s if there is no cheater or s
′ ≠s if cheaters exist
Process
(i)
C reconstructs f
′(x) from (i, v
i) using Lagrange interpolation (19)
f
′
x
=
∑
i
=
1
t
v
i
∏
j
=
1
,
j
≠
i
t
x
i
-
x
x
i
-
x
j
(ii)
C outputs polynomial f
′(x) = a
0
′ + a
1
′
x + a
2
′
x
2 + … + a
t
-
1
′
x
t-1.
By Theorem11, the reconstructed polynomial f
′(x) is unique and if there is no cheating then polynomial f
′(x) is equal to polynomialf(x). Therefore, the secret is f
′(0) = a
0
′ = s
′ =s.Cheating Detection. It is important to check if there are forged shares presented during secret reconstruction. In this phase, PBLS uses basic scheme to reveal the secret since it is hidden in the coefficient of x of the polynomialf(x). Consequently, the polynomial f
′(x) should have the same coefficient. The secret is revealed by multiplying the coefficient of x by a multiplicative inverse of an element r. If the result gives term a
0
′, then there is no cheating. Therefore, the secret is valid. Otherwise, some forged shares are used during reconstruction of the secret. Algorithm 30 shows how cheating detection is done.Algorithm 30 (cheating detection).
Input. Elements z andb
Output. No cheating or cheating
Process
(i)
C computesb·z = a
0
′.
(ii)
C outputs no cheating if a
0
′ holds or cheating otherwise.
C uses Algorithm 30 to detect if forged shares were presented to reconstruct the secret.C uses multiply a
1
′ by b to get a
0
′. Once the output is not a
0
′, then cheating took place, secret reconstruction halted, and the reconstructed secret was not valid.C sends to users a signal that secret reconstruction has failed. In cases where all users are honest, Algorithm 30 outputs no cheating. Consequently, the output Algorithm 29 valid and C sends a
0
′ to each user, which shows that secret reconstruct is successful. A simple example below demonstrates how the new scheme works.Example 31.
Letp = 23. Given the secrets = 12, we can share it ton= 6 users such that anyt = 4 of them can reconstruct the secret.
We use Algorithm25 to hide the secret and select a randomr ∈
F
23 as 15(20)
z
≡
s
·
r
m
o
d
p
≡
12
·
15
m
o
d
23
≡
19
.
We also compute a multiplicative inverse ofr.(21)
b
≡
r
-
1
m
o
d
p
≡
15
-
1
m
o
d
23
≡
20
m
o
d
23
.
Let the random polynomial be(22)
f
x
=
12
+
19
x
+
20
x
2
+
9
x
3
.
The shares given to users are(23)
U
1
:
f
1
=
12
+
19
×
1
+
20
×
1
2
+
9
×
1
3
=
14
U
2
:
f
2
=
12
+
19
×
2
+
20
×
2
2
+
9
×
2
3
=
18
U
3
:
f
3
=
12
+
19
×
3
+
20
×
3
2
+
9
×
3
3
=
9
U
4
:
f
4
=
12
+
19
×
4
+
20
×
4
2
+
9
×
4
3
=
18
U
5
:
f
5
=
12
+
19
×
5
+
20
×
5
2
+
9
×
5
3
=
7
U
6
:
f
6
=
12
+
19
×
6
+
20
×
6
2
+
9
×
6
3
=
7
.
Each user also receives 20 a multiplicative inverse of 15∈
F
23.
When the secret is required, any 4 users send their shares toC to reconstruct the secret s. Let U
1, U
3, U
5, and U
6 send their shares to C. We use Lagrange interpolation to reconstruct a polynomial f
′(x). We find the g
i(x) ∀i = {
0, 1, 2, 3
} as discussed in Section 2.1.3
(24)
g
0
x
=
x
-
3
x
-
5
x
-
6
1
-
3
1
-
5
1
-
6
=
4
x
3
+
9
x
2
+
17
x
+
2
=
4
x
3
+
13
x
2
+
22
x
+
8
g
1
x
=
x
-
1
x
-
5
x
-
6
3
-
1
3
-
5
3
-
6
=
2
x
3
+
11
x
2
+
18
x
+
16
=
2
x
3
+
22
x
2
+
13
x
+
9
g
2
x
=
x
-
1
x
-
3
x
-
6
5
-
1
5
-
3
5
-
6
=
20
x
3
+
13
x
2
+
4
x
+
5
=
20
x
3
+
7
x
2
+
11
x
+
8
g
3
x
=
x
-
1
x
-
3
x
-
5
6
-
1
6
-
3
6
-
5
=
20
x
3
+
14
x
2
+
8
=
20
x
3
+
4
x
2
+
22
.
Therefore, the polynomialf
′(x) is(25)
f
′
x
=
f
1
g
0
x
+
f
3
g
1
x
+
f
5
g
2
x
+
f
6
g
3
x
=
14
4
x
3
+
13
x
2
+
22
x
+
8
+
9
2
x
3
+
22
x
2
+
13
x
+
9
+
7
20
x
3
+
7
x
2
+
11
x
+
8
+
7
20
x
3
+
4
x
2
+
22
=
9
x
3
+
20
x
2
+
19
x
+
12
The polynomialf
′(x) = 9x
3 + 20x
2 + 19x +12 is the same used to share the secret. Cheating detection is done by multiplying 19 by 20, which gives 12. Assuming users U
1, U
3, and U
5 want to cheat U
6. Let the forged shares be U
1: (1, 8), U
3: (3, 10), U
5: (5, 17) and U
6: (6, 7).C reconstructs a polynomial(26)
f
′
x
=
3
x
3
+
11
x
2
+
10
x
+
7
.
Multiplying 11 by 20 gives 12, which is not equal to 7. Cheating is detected by cheating detection algorithm in PBLS.


## 3.2.1. Basic Scheme

This subsection proposes basic scheme, which is the basis for constructing PBLS proposed in Section3.2.2. Basic scheme provides a conceptual process of how PBLS detects cheating during secret reconstruction. A secret is hidden by a field element r and can be revealed by a multiplicative inverse b of the elementr.Secret Hiding. Consider a finite field F
p in which p is a prime such thatp - 1 has at least one large prime factor. Ifp - 1 has only small prime factors, then computing FFDLP is easy as pointed out by [5]. By Proposition 3, all nonzero elements a in F
p have a multiplicative inverse b such thata·b ≡ 1 mod p. A secret s is also the field element ass∈
F
p. Any random number r except 1 can be used to hide the secret s. The algorithm for hiding the secret avoids using 1 because it is a multiplicative identity therefore cannot hide s. After multiplying r bys, a different field element z is obtained. Hence Equation (13) follows(13)
z
≡
r
·
s
m
o
d
p
.Algorithm25 describes how a secret s is hidden using field element in basic scheme.Algorithm 25 (secret hiding).
Input. Secrets
Output. Elementz
Process
(i)
Choose a random elementr∈
Z
p.
(ii)
Computez by multiplying r bys.
(iii)
Output elementz∈
Z
p.
Figure2 illustrates how Algorithm 25 works.
The elementz does not reveal any information of s and r in basic scheme.Figure 2
Secret hiding in basic scheme.Secret Revealing. Whenever one wants the secret s back, he (or she) simply computes the multiplicative inverse ofr, given as b, and multiplies it by z to get the secret s. Therefore, multiplying z by multiplicative inverse of r is the same as multiplying r byr
−1 by s. This means 1 is multiplied by s to get a result s as in Equation (14)(14)
s
≡
b
·
z
m
o
d
p
≡
r
-
1
·
r
·
s
m
o
d
p
≡
s
m
o
d
p
.Algorithm26 shows how to reveal the secret s using the multiplicative inverse ofr.Algorithm 26 (secret revealing).
Input. Elements z andr
Output. Secrets
Process
(i)
Compute multiplicative inverseb of elementr, i.e.,b=r
−1.
(ii)
Computes by multiplying b byz.
(iii)
Outputs.
Figure3 illustrates Algorithm 26: how revealing the secret occurs.Figure 3
Secret revealing in basic scheme.Basic scheme requiresr to be kept secret so that the secret remains private and secure. Otherwise, any adversary will be able to compute the inverse of r and reveal s as is done in Algorithm 26. We demonstrate this with a dummy example below.Example 27.
Letp = 23 ands = 12. Secret s can be hidden as follows. Choose a random elementr = 7 ∈
Z
23. Compute z by multiplying r by s to obtainz
(15)
z
≡
r
·
s
m
o
d
23
≡
7
·
12
m
o
d
23
≡
15
m
o
d
23
.
The secret 12 is hidden as 15. It is difficult for an adversaryA to know the secret 12 and the random 7 from 15 alone unless he (or she) solves FFDLP. The secret s is revealed by computingb, the multiplicative inverse ofr
(16)
b
=
r
-
1
=
10
,and computing s by multiplying y byz
(17)
s
≡
b
·
z
m
o
d
23
≡
10
·
15
m
o
d
23
≡
12
m
o
d
23
.
Note that in practice,p should be a large prime number for the scheme to be secure enough.


## 3.2.2. Polynomial Based Linear Scheme (PBLS)

In this subsection, a linear (t,n) threshold secret sharing scheme, PBLS, is proposed, which provides cheating detection based on basic scheme and Shamir’s secret sharing. We assume using two trusted third parties dealer D and combinerC.D generates and distributes shares to n users while C collects any t shares and reconstructs the secret. A trusted user can also be C depending on the application.C does not reveal shares after reconstruction and hence performs a closed reconstruction. In addition,C performs cheating detection in secret reconstruction phase. PBLS has three algorithms, which are share generation, secret reconstruction, and cheating detection.Share Generation. As Shamir’s scheme, share generation algorithm starts with D setting public parameters, prime p and thresholdt.D chooses a random element r from a finite field F
p, then hides the secret using Algorithm 25. The output is elementz∈
F
p.D computesb∈
F
p, a multiplicative inverse of r. The element b is sent to n users on public channel while element z becomes a coefficient of x in polynomialf(x). To share the secrets,D chooses a random polynomial of degreet - 1, which has constraints of two coefficients, a
0 =s and a
1 =z.D computesf(i) for alli = 1, 2, …,n and distributes v
i = (i,f(i)) to users wherei = 1, 2, …,n. Algorithm 28 shows how shares are generated and distributed to users.Algorithm 28 (share generation).
Input. Secrets
Output. Secret shares v
i wherei = 1, 2, …,n
Process
(i)
D uses Algorithm 25 to computez.
(ii)
D uses Algorithm 26 to computeb.
(iii)
D chooses a random polynomialf(x) of degreet - 1 over F
p, i.e.,(18)
f
x
=
a
0
+
a
1
x
+
a
2
x
2
+
…
+
a
t
-
1
x
t
-
1
such thata
0 =s and a
1 =z.
(iv)
D computesf(i) and distributes v
i = (i,f(i)) and b to U
i for alli = 1, 2, …,n secretly.
Figure4 illustrates the share generation algorithm in PBLS.
Users cannot obtain information of the secrets from z without the knowledge of r unless they have to solve FFDLP.Figure 4
Share generation in PBLS.Secret Reconstruction. If the secret is required for use, anyt ≤n users combine their shares together to reconstruct it. The combiner can be one of the user or a trusted third party who does the reconstruction without revealing the shares. Users send their shares to C together withb.C uses Lagrange interpolation to reconstruct the polynomial of degreet - 1 from at least t points, i.e., (1,f(1)), (2,f(2)), … (i,f(i)) and the secret isf(0) if all users are honest. Figure 5 illustrates how secret reconstruction is done in PBLS.Figure 5
Secret reconstruction in PBLS.Algorithm 29 (secret reconstruction).
Input. Any list of t shares
Output. Secret s
′ =s if there is no cheater or s
′ ≠s if cheaters exist
Process
(i)
C reconstructs f
′(x) from (i, v
i) using Lagrange interpolation (19)
f
′
x
=
∑
i
=
1
t
v
i
∏
j
=
1
,
j
≠
i
t
x
i
-
x
x
i
-
x
j
(ii)
C outputs polynomial f
′(x) = a
0
′ + a
1
′
x + a
2
′
x
2 + … + a
t
-
1
′
x
t-1.
By Theorem11, the reconstructed polynomial f
′(x) is unique and if there is no cheating then polynomial f
′(x) is equal to polynomialf(x). Therefore, the secret is f
′(0) = a
0
′ = s
′ =s.Cheating Detection. It is important to check if there are forged shares presented during secret reconstruction. In this phase, PBLS uses basic scheme to reveal the secret since it is hidden in the coefficient of x of the polynomialf(x). Consequently, the polynomial f
′(x) should have the same coefficient. The secret is revealed by multiplying the coefficient of x by a multiplicative inverse of an element r. If the result gives term a
0
′, then there is no cheating. Therefore, the secret is valid. Otherwise, some forged shares are used during reconstruction of the secret. Algorithm 30 shows how cheating detection is done.Algorithm 30 (cheating detection).
Input. Elements z andb
Output. No cheating or cheating
Process
(i)
C computesb·z = a
0
′.
(ii)
C outputs no cheating if a
0
′ holds or cheating otherwise.
C uses Algorithm 30 to detect if forged shares were presented to reconstruct the secret.C uses multiply a
1
′ by b to get a
0
′. Once the output is not a
0
′, then cheating took place, secret reconstruction halted, and the reconstructed secret was not valid.C sends to users a signal that secret reconstruction has failed. In cases where all users are honest, Algorithm 30 outputs no cheating. Consequently, the output Algorithm 29 valid and C sends a
0
′ to each user, which shows that secret reconstruct is successful. A simple example below demonstrates how the new scheme works.Example 31.
Letp = 23. Given the secrets = 12, we can share it ton= 6 users such that anyt = 4 of them can reconstruct the secret.
We use Algorithm25 to hide the secret and select a randomr ∈
F
23 as 15(20)
z
≡
s
·
r
m
o
d
p
≡
12
·
15
m
o
d
23
≡
19
.
We also compute a multiplicative inverse ofr.(21)
b
≡
r
-
1
m
o
d
p
≡
15
-
1
m
o
d
23
≡
20
m
o
d
23
.
Let the random polynomial be(22)
f
x
=
12
+
19
x
+
20
x
2
+
9
x
3
.
The shares given to users are(23)
U
1
:
f
1
=
12
+
19
×
1
+
20
×
1
2
+
9
×
1
3
=
14
U
2
:
f
2
=
12
+
19
×
2
+
20
×
2
2
+
9
×
2
3
=
18
U
3
:
f
3
=
12
+
19
×
3
+
20
×
3
2
+
9
×
3
3
=
9
U
4
:
f
4
=
12
+
19
×
4
+
20
×
4
2
+
9
×
4
3
=
18
U
5
:
f
5
=
12
+
19
×
5
+
20
×
5
2
+
9
×
5
3
=
7
U
6
:
f
6
=
12
+
19
×
6
+
20
×
6
2
+
9
×
6
3
=
7
.
Each user also receives 20 a multiplicative inverse of 15∈
F
23.
When the secret is required, any 4 users send their shares toC to reconstruct the secret s. Let U
1, U
3, U
5, and U
6 send their shares to C. We use Lagrange interpolation to reconstruct a polynomial f
′(x). We find the g
i(x) ∀i = {
0, 1, 2, 3
} as discussed in Section 2.1.3
(24)
g
0
x
=
x
-
3
x
-
5
x
-
6
1
-
3
1
-
5
1
-
6
=
4
x
3
+
9
x
2
+
17
x
+
2
=
4
x
3
+
13
x
2
+
22
x
+
8
g
1
x
=
x
-
1
x
-
5
x
-
6
3
-
1
3
-
5
3
-
6
=
2
x
3
+
11
x
2
+
18
x
+
16
=
2
x
3
+
22
x
2
+
13
x
+
9
g
2
x
=
x
-
1
x
-
3
x
-
6
5
-
1
5
-
3
5
-
6
=
20
x
3
+
13
x
2
+
4
x
+
5
=
20
x
3
+
7
x
2
+
11
x
+
8
g
3
x
=
x
-
1
x
-
3
x
-
5
6
-
1
6
-
3
6
-
5
=
20
x
3
+
14
x
2
+
8
=
20
x
3
+
4
x
2
+
22
.
Therefore, the polynomialf
′(x) is(25)
f
′
x
=
f
1
g
0
x
+
f
3
g
1
x
+
f
5
g
2
x
+
f
6
g
3
x
=
14
4
x
3
+
13
x
2
+
22
x
+
8
+
9
2
x
3
+
22
x
2
+
13
x
+
9
+
7
20
x
3
+
7
x
2
+
11
x
+
8
+
7
20
x
3
+
4
x
2
+
22
=
9
x
3
+
20
x
2
+
19
x
+
12
The polynomialf
′(x) = 9x
3 + 20x
2 + 19x +12 is the same used to share the secret. Cheating detection is done by multiplying 19 by 20, which gives 12. Assuming users U
1, U
3, and U
5 want to cheat U
6. Let the forged shares be U
1: (1, 8), U
3: (3, 10), U
5: (5, 17) and U
6: (6, 7).C reconstructs a polynomial(26)
f
′
x
=
3
x
3
+
11
x
2
+
10
x
+
7
.
Multiplying 11 by 20 gives 12, which is not equal to 7. Cheating is detected by cheating detection algorithm in PBLS.


## 4. Analysis

This section provides the analysis of basic scheme and PBLS in terms of security and privacy with required features and computational overhead. We also compare the security, privacy, and computations in PBLS to Shamir’s scheme and Liu et al.’s scheme [6, 14]. PBLS achieves the required features for the secret sharing schemes like SP1, SP2, SP3, SP4, and CO. Proofs for these requirements are provided. For this, we first provide the proof for the security of basic scheme, which is used by PBLS to detect cheating. The section also provides the proof of how secure PBLS is against cheating based on the assumption of OKS because the aim of secret sharing is to make the secret not known to users until reconstruction.


### 4.1. Security and Privacy Analysis

This subsection provides the analysis on the security and privacy of PBLS and proves that the required features for secret sharing schemes are achieved. We show that PBLS achieves the following properties.(i)
SP1: the secret is not known to all users and adversaryA before reconstruction.
(ii)
SP2: the secret can be reconstructed once it is shared ton users.
(iii)
SP3: no less than required number of users can reconstruct the secret.
(iv)
SP4: this is based on OKS assumption, which provides the guarantee that no cheating can be successful in PBLS.First, we show that basic scheme is secure fromA based on OKS adversary model in Section 3.1.3. At initialization of basic scheme, the secret is multiplied by a random element r with an aim of hiding it. Two security issues rise up in this case:(i)
security ofs in z for the basic scheme and
(ii)
security ofs in the polynomialf(x).Proposition32 proves the security of basic scheme from any adversary, i.e., dishonest user or anyone who is not taking part in the secret sharing cannot obtain the secret s without the knowledge of r and its multiplicative inverse.Proposition 32.
Letp be prime andz≡s·r
m
o
d
p such thats∈
Z
p andr ∈
Z
p are a secret and a random number, respectively. An adversary A should solve FFDLP to obtain the secret from z in basic scheme without the knowledge of r and its multiplicative inverse.Proof.
We showed in Proposition19 that an element z cannot reveal any information about s without the knowledge of r. It was indicated that it is necessary to solve FFDLP to reveal s from z. Therefore, to know the secret from z in basic scheme, one has to solve FFDLP. Basic scheme is secure from A.However, we also need to show that the secret cannot be revealed byA inz, which is the polynomial used to distribute shares to users. Proposition 33 proves that basic scheme is secure in share generation algorithm.Proposition 33.
Letz,s, and r
∈
Z
p as defined in Proposition 32 and p be prime. An adversary A should solve FFDLP to obtain the secret from z in the polynomialf(x) even if multiplicative inverse of r is known.Proof.
By Proposition19, it is difficult to obtain s from z without the knowledge of r. However, if r is known, the secret s can be obtained. During share generation all users have access to the multiplicative inverse of r and their share; hence, it is possible to obtain the secret if z is known. However, the secret and the element z are coefficients of the polynomial, which are only known to the dealer. But the multiplicative inverse of r cannot give information of s and z. This is the same as solving the FFDLP.Security of secret sharing schemes depends on the private distribution of shares to user so that no user should know the shares of the other users. Therefore, each user has to receive the share from the dealer using a private channel. It is assumed that users do not communicate about their shares to each other unless they collaborate to cheat. Once the secret is divided, the shares do not show any information about the secret. As a result users do not have any information about the secret as assumed by OKS. In addition to this, shares are delivered privately to users and hence cannot know the share of the other users. Lemma34 proves the fact of SP1 that users do not have access to the secret.Lemma 34.
Any secret share given to a participant in PBLS does not reveal the secrets.Proof.
In share generation, PBLS uses Shamir’s method to share the secret, which uses the polynomialf(x) of degreet - 1. Each share is evaluated from i to givef(i) for alli > 0 such that i is the identity of the user. The secret in the polynomial isf(0). Shares in Shamir’s scheme do not reveal any information of the secret. Since PBLS adopts Shamir’s method, the shares generated have the same security as those generated by Shamir’s scheme.Lemma34 proves that no single user can have access to the secret using only his (or her) share. However, the secret can be reconstructed if t users pool in their shares together. Since the reconstruction is done by a trusted third party called combiner, no user is able to know the secret. However, the secret is obtained by the combiner. We now prove Proposition 35, which gives a proof on SP2 in PBLS.Proposition 35.
Lett be the threshold. Any t users can reconstruct the secret by combining their shares together in PBLS by using secret reconstruction algorithm.Proof.
Secret reconstruction in PBLS is done by interpolating the polynomialf
′(x) by Lagrange interpolation. Given t points (i, v
i) for alli =1, 2, …,t, interpolated polynomial as in Equation (19). We rewrite the Equation below for clarity(27)
f
′
x
=
∑
i
=
1
t
v
i
∏
j
=
1
,
j
≠
i
t
x
-
x
j
x
i
-
x
j
=
∑
i
=
0
t
-
1
a
i
′
x
i
.
By Theorem11 the polynomial f
′(x) is unique which has degreet - 1. The dealer used Equation (18) to generate shares and we write it(28)
f
x
=
∑
i
=
0
t
-
1
a
i
x
i
.
Therefore, the two polynomials in Equations (27) and (28) are equal. By Definition 7, a
i = a
i
′. So, a
0 = a
0
′. Since a
0 is the secret, a
0
′ is also a secret, which has been reconstructed from t shares. Therefore, the secret in PBLS can be reconstructed.Ift shares can reveal the secret, then less than t shares should not be able to show any information about the secret. This is the recommendation of a secret sharing scheme to be achieved, which is called privacy. Proposition 36 proves SP3 of PBLS such that less than the required threshold can neither recover the secret not gain information about the secret.Proposition 36.
Lett be the threshold. Less than t users cannot reconstruct or know any information of the secret in PBLS.Proof.
We need to show thatt - 1 shares do not reveal any information about the secret. Assumet - 1 participants collude to recover the secret, which means they will havet - 1 points to interpolate a polynomial f
′(x) of degreet - 1. However, these points will interpolate a polynomial of degreet - 2 as far as Theorem 11 is concerned, hence(29)
f
′
x
=
∑
i
=
1
t
-
1
v
i
∏
j
=
1
,
j
≠
i
t
-
1
x
-
x
j
x
i
-
x
j
=
∑
i
=
0
t
-
2
a
i
′
x
i
.
Equations (27) and (28) are not equal since they have different degrees. The fact that polynomial in Equation (29) is unique makes their coefficient differ as well. The other way is to try to solve a system oft - 1 equations with t unknowns as shown in the matrix Equation (30). (30)
1
I
D
1
…
I
D
1
t
-
1
1
I
D
2
…
I
D
2
t
-
1
⋮
⋮
…
⋮
1
I
D
t
-
1
…
I
D
t
-
1
t
-
1
a
0
a
1
⋮
a
t
-
1
=
f
I
D
1
f
I
D
2
⋮
f
I
D
t
-
1
But it is impossible to solve such equations unless thet-th term is guessed. Thus, we need at least t points to interpolate the polynomial, which might be not correct since thet-th share is secretly delivered to user. By Lemma 34, each share does not reveal the information about the secret. Therefore,t - 1 shares cannot reveal any information about the secret in PBLS.During secret reconstruction,t - 1 users may collude to cheat thet-th user. Since the aim of the cheaters is to prevent the correct recovery of the secret at the same time they should be able to reconstruct the valid secret. This is avoided in PBLS because all shares from participating users are not revealed during secret reconstruction. Therefore, ift - 1 users communicated their shares, it will be difficult to reconstruct the secret without thet-th share as proved in Proposition 35. Furthermore, PBLS will be able to detect cheating ift - 1 or less shares are forged. Proposition 37 proves that no cheating can be successful in PBLS even ift - 1 forged shares were presented during secret reconstruction.Proposition 37.
Lett be the threshold andt - 1 be forged shares presented to the combiner. The forged shares will be detected during secret reconstruction in PBLS.Proof.
Once fake shares are pooled to the combiner, the combiner uses Lagrange interpolation to compute a polynomialf
′(x) of degreet - 1, which is unique; hence f
′(x) ≠f(x). After coming up with the polynomial, the combiner will use the multiplicative inverse of the random elementr
−1
∈
F
p to verify the secret as follows: (31)
z
·
r
≡
s
·
r
·
r
-
1
m
o
d
p
≡
s
m
o
d
p
,where s is the coefficient of x
0. This works by Proposition 3. Since forged shares are used in secret reconstruction, the interpolated polynomial f
′(x) will not be equal to the polynomial used by the dealer in share generation algorithm; therefore, a
i
′ ≠ a
i. Equation (31) will not work; thusz·r
−1 ≠s. Therefore, cheating is detected in PBLS.PBLS achieves the share size of|
v
i
| = |
s
| /ε such that ε > 0 is the probability for successful cheating. Theorem 38 provides the security of PBLS and a proof on the share size of PBLS [30–39].Theorem 38.
PBLS described in Section3.2.2 realizing the access structure Γ is ε-secure against up tot - 1 cheaters who may somehow know the secret beforehand. Moreover, the share size is |
v
i
|
=
p
2 = |
s
| /ε, where ε =1/p and v
i denotes the share space of thei-th participant U
i.Proof.
Sincep is prime, Z
p is a finite field. We let the secret to be p bits long so(32)
s
=
p
.
For successful cheating, an adversaryA has the sample space of p. Hence the probability is(33)
ε
=
1
p
.
Since every user receivesf(i) andy, the share is(34)
v
i
=
f
i
,
y
w
h
e
r
e
y
=
r
-
1
.
So|
f
(
i
)
| =p and |
y
| =p. Therefore,(35)
v
i
=
p
2
.
From Equations (32) and (33), (36)
s
p
=
ε
p
.
This implies that(37)
s
ε
=
p
2
.
From Equation (35)(38)
v
i
=
p
2
=
s
ε
.
Suppose an honest participantU
h having the share v
h
= (h,f(h) ) belongs to thek-th compartment. For a valid but incorrect secret s
′
∈ S to be accepted by U
h, after parsing another check polynomial g
′(x) with g
′(0) = s
′, the point (x
h,g(x
h)) should lie on the polynomial g
′(x). So, the successful cheating probability (PBLS, A) of cheaters A against PBLS is defined as(39)
ε
P
B
L
S
,
A
=
Pr
⁡
g
′
x
p
a
s
s
e
s
t
h
r
o
u
g
h
a
p
o
i
n
t
x
h
,
g
x
h
u
n
k
n
o
w
n
t
o
A
.
Since is a polynomialg(x) of degreet - 1 over F
p from different constant term, ε =1/p. This proves the theorem.Propositions35 and 36 indicate that PBLS is perfect since the secret can be recovered by the required threshold but not less. This is the same for Shamir’s scheme and Liu et al.’s scheme. Theorem 38 indicates that any cheating behavior can be detected, which is similar to Liu et al.’s scheme. Furthermore, PBLS and Liu et al.’s scheme have the same share size given to users. Therefore, PBLS and Liu et al.’s scheme have the same property of cheating detection.We now compare the security and properties of PBLS with Shamir’s scheme and Liu et al.’s scheme. Table1 shows that comparison of SPs and CO of these schemes.Table 1
Comparison of required properties for the schemes.
Scheme
Property
SP1
SP2
SP3
SP4
CO
Shamir’s scheme
√
√
√
X
1
Liu et al.’s scheme
√
√
√
√
2
PBLS
√
√
√
√
1
√: the property exists; X: the property does not exist.Table1 shows that the schemes have similar properties in terms of SP1, SP2, and SP3. However, Shamir’s scheme does not provide SP4. It also shows that PBLS achieves CO simultaneously. Even if PBLS provides good aspects in security and privacy, we need to mention that there is possibility that shareholders have some advantages over learning the secret since they have b as mentioned in Algorithm 28. So, our future research should focus on devising a new scheme to solve this probability.


### 4.2. Computation Analysis

In this subsection, we analyze the computation overhead of PBLS and give a comparison to Shamir’s scheme and Liu et al.’s scheme. Three operations are used in this analysis, which are modulo addition (add), modulo multiplication (mul), and modulo inverse (inv). The analysis will consider all the two algorithms. However Algorithm25 of basic scheme is not considered in this analysis since it is an initialization phase of PBLS.


#### 4.2.1. Computations in PBLS

In PBLS, a share is computed from a polynomialf(x) of degreet - 1. Therefore, the polynomial has t terms andt - 1 of them are multiplied by a variable x. Each share requires modulo addition and modulo multiplication to be computed. Therefore, Table 2 shows computation in share generation of PBLS.Table 2
Computations in share generation of PBLS.
Share generation
Operation
mul
add
inv
Total
Number of operations
n(t -1)
nt
-
n(t -1) mul + nt addThe aim of secret reconstruction is to come up with a secret, which is done using Lagrange interpolation. A polynomial is interpolated usingt points, which are the shares and the identity of the user, i.e., (i, v
i). The polynomial f
′(x) is obtained as in Equation (27), which is rewritten as(40)
f
′
x
=
∑
i
=
1
t
v
i
·
p
i
x
,
w
h
e
r
e
p
i
x
=
∏
j
=
1
,
j
≠
i
t
x
-
x
j
x
i
-
x
j
.To compute eachp
i(x), Table 3 shows the computations in secret reconstruction of PBLS.Table 3
Computations in secret reconstruction of PBLS.
Secret reconstruction
Operation
mul
add
inv
Total
Number of operations
t
3 + t + 1
t
t
(t
3 + t + 1) mul + t add + t inv


#### 4.2.2. Comparison

Now, we compare the computation overhead of PBLS with Shamir’s scheme and Liu et al.’s scheme. We follow the method done in Section4.2.1 to provide computation overhead comparison. Table 4 shows the computation overhead comparisons in share generation phase and secret reconstruction phase.Table 4
Computation overhead of related schemes.
Share generation
Scheme
Operation
mul
add
inv
Total
Liu et al.’s scheme
2n(t - 1)
2nt
-
2n(t - 1) mul + 2nt add
Shamir’s scheme
n(t - 1)
nt
-
n(t - 1) mul + nt add
PBLS
n(t - 1)
nt
-
n(t - 1) mul + nt add
Secret reconstruction
Scheme
Operation
mul
add
inv
Total
Liu et al.’s scheme
2(t
3 + t + 1)
2t
2t
2(t
3 + t + 1) mul + 2t add + 2t inv
Shamir’s scheme
t
3 + t + 1
t
t
(t
3 + t) mul + t add + t inv
PBLS
t
3 + t + 1
t
t
(t
3 + t + 1) mul + t add + t invResults in Table4 show that PBLS and Shamir’s scheme have the same computation overhead at share generation phase. The result is due to the use of a single polynomial when sharing and distributing the secret to users. However, comparing this result to Liu et al.’s scheme, the computation overhead is reduced by half in share generation phase. This indicates that PBLS has an efficient way to share the secret as compared to Liu et al.’s scheme but comparable with Shamir’s scheme.Considering secret reconstruction process, computation overhead on PBLS is higher by 1 mul as compared to Shamir’s scheme. This is so because of cheating detection in PBLS in which the operation is 1 mul but Shamir’s scheme does not have. However, results show that computation overhead of Liu et al.’s scheme at secret reconstruction still doubles as compared to PBLS. Therefore, PBLS is more efficient as compared to Liu et al.’s scheme in the concern of computation overhead.


## 4.1. Security and Privacy Analysis

This subsection provides the analysis on the security and privacy of PBLS and proves that the required features for secret sharing schemes are achieved. We show that PBLS achieves the following properties.(i)
SP1: the secret is not known to all users and adversaryA before reconstruction.
(ii)
SP2: the secret can be reconstructed once it is shared ton users.
(iii)
SP3: no less than required number of users can reconstruct the secret.
(iv)
SP4: this is based on OKS assumption, which provides the guarantee that no cheating can be successful in PBLS.First, we show that basic scheme is secure fromA based on OKS adversary model in Section 3.1.3. At initialization of basic scheme, the secret is multiplied by a random element r with an aim of hiding it. Two security issues rise up in this case:(i)
security ofs in z for the basic scheme and
(ii)
security ofs in the polynomialf(x).Proposition32 proves the security of basic scheme from any adversary, i.e., dishonest user or anyone who is not taking part in the secret sharing cannot obtain the secret s without the knowledge of r and its multiplicative inverse.Proposition 32.
Letp be prime andz≡s·r
m
o
d
p such thats∈
Z
p andr ∈
Z
p are a secret and a random number, respectively. An adversary A should solve FFDLP to obtain the secret from z in basic scheme without the knowledge of r and its multiplicative inverse.Proof.
We showed in Proposition19 that an element z cannot reveal any information about s without the knowledge of r. It was indicated that it is necessary to solve FFDLP to reveal s from z. Therefore, to know the secret from z in basic scheme, one has to solve FFDLP. Basic scheme is secure from A.However, we also need to show that the secret cannot be revealed byA inz, which is the polynomial used to distribute shares to users. Proposition 33 proves that basic scheme is secure in share generation algorithm.Proposition 33.
Letz,s, and r
∈
Z
p as defined in Proposition 32 and p be prime. An adversary A should solve FFDLP to obtain the secret from z in the polynomialf(x) even if multiplicative inverse of r is known.Proof.
By Proposition19, it is difficult to obtain s from z without the knowledge of r. However, if r is known, the secret s can be obtained. During share generation all users have access to the multiplicative inverse of r and their share; hence, it is possible to obtain the secret if z is known. However, the secret and the element z are coefficients of the polynomial, which are only known to the dealer. But the multiplicative inverse of r cannot give information of s and z. This is the same as solving the FFDLP.Security of secret sharing schemes depends on the private distribution of shares to user so that no user should know the shares of the other users. Therefore, each user has to receive the share from the dealer using a private channel. It is assumed that users do not communicate about their shares to each other unless they collaborate to cheat. Once the secret is divided, the shares do not show any information about the secret. As a result users do not have any information about the secret as assumed by OKS. In addition to this, shares are delivered privately to users and hence cannot know the share of the other users. Lemma34 proves the fact of SP1 that users do not have access to the secret.Lemma 34.
Any secret share given to a participant in PBLS does not reveal the secrets.Proof.
In share generation, PBLS uses Shamir’s method to share the secret, which uses the polynomialf(x) of degreet - 1. Each share is evaluated from i to givef(i) for alli > 0 such that i is the identity of the user. The secret in the polynomial isf(0). Shares in Shamir’s scheme do not reveal any information of the secret. Since PBLS adopts Shamir’s method, the shares generated have the same security as those generated by Shamir’s scheme.Lemma34 proves that no single user can have access to the secret using only his (or her) share. However, the secret can be reconstructed if t users pool in their shares together. Since the reconstruction is done by a trusted third party called combiner, no user is able to know the secret. However, the secret is obtained by the combiner. We now prove Proposition 35, which gives a proof on SP2 in PBLS.Proposition 35.
Lett be the threshold. Any t users can reconstruct the secret by combining their shares together in PBLS by using secret reconstruction algorithm.Proof.
Secret reconstruction in PBLS is done by interpolating the polynomialf
′(x) by Lagrange interpolation. Given t points (i, v
i) for alli =1, 2, …,t, interpolated polynomial as in Equation (19). We rewrite the Equation below for clarity(27)
f
′
x
=
∑
i
=
1
t
v
i
∏
j
=
1
,
j
≠
i
t
x
-
x
j
x
i
-
x
j
=
∑
i
=
0
t
-
1
a
i
′
x
i
.
By Theorem11 the polynomial f
′(x) is unique which has degreet - 1. The dealer used Equation (18) to generate shares and we write it(28)
f
x
=
∑
i
=
0
t
-
1
a
i
x
i
.
Therefore, the two polynomials in Equations (27) and (28) are equal. By Definition 7, a
i = a
i
′. So, a
0 = a
0
′. Since a
0 is the secret, a
0
′ is also a secret, which has been reconstructed from t shares. Therefore, the secret in PBLS can be reconstructed.Ift shares can reveal the secret, then less than t shares should not be able to show any information about the secret. This is the recommendation of a secret sharing scheme to be achieved, which is called privacy. Proposition 36 proves SP3 of PBLS such that less than the required threshold can neither recover the secret not gain information about the secret.Proposition 36.
Lett be the threshold. Less than t users cannot reconstruct or know any information of the secret in PBLS.Proof.
We need to show thatt - 1 shares do not reveal any information about the secret. Assumet - 1 participants collude to recover the secret, which means they will havet - 1 points to interpolate a polynomial f
′(x) of degreet - 1. However, these points will interpolate a polynomial of degreet - 2 as far as Theorem 11 is concerned, hence(29)
f
′
x
=
∑
i
=
1
t
-
1
v
i
∏
j
=
1
,
j
≠
i
t
-
1
x
-
x
j
x
i
-
x
j
=
∑
i
=
0
t
-
2
a
i
′
x
i
.
Equations (27) and (28) are not equal since they have different degrees. The fact that polynomial in Equation (29) is unique makes their coefficient differ as well. The other way is to try to solve a system oft - 1 equations with t unknowns as shown in the matrix Equation (30). (30)
1
I
D
1
…
I
D
1
t
-
1
1
I
D
2
…
I
D
2
t
-
1
⋮
⋮
…
⋮
1
I
D
t
-
1
…
I
D
t
-
1
t
-
1
a
0
a
1
⋮
a
t
-
1
=
f
I
D
1
f
I
D
2
⋮
f
I
D
t
-
1
But it is impossible to solve such equations unless thet-th term is guessed. Thus, we need at least t points to interpolate the polynomial, which might be not correct since thet-th share is secretly delivered to user. By Lemma 34, each share does not reveal the information about the secret. Therefore,t - 1 shares cannot reveal any information about the secret in PBLS.During secret reconstruction,t - 1 users may collude to cheat thet-th user. Since the aim of the cheaters is to prevent the correct recovery of the secret at the same time they should be able to reconstruct the valid secret. This is avoided in PBLS because all shares from participating users are not revealed during secret reconstruction. Therefore, ift - 1 users communicated their shares, it will be difficult to reconstruct the secret without thet-th share as proved in Proposition 35. Furthermore, PBLS will be able to detect cheating ift - 1 or less shares are forged. Proposition 37 proves that no cheating can be successful in PBLS even ift - 1 forged shares were presented during secret reconstruction.Proposition 37.
Lett be the threshold andt - 1 be forged shares presented to the combiner. The forged shares will be detected during secret reconstruction in PBLS.Proof.
Once fake shares are pooled to the combiner, the combiner uses Lagrange interpolation to compute a polynomialf
′(x) of degreet - 1, which is unique; hence f
′(x) ≠f(x). After coming up with the polynomial, the combiner will use the multiplicative inverse of the random elementr
−1
∈
F
p to verify the secret as follows: (31)
z
·
r
≡
s
·
r
·
r
-
1
m
o
d
p
≡
s
m
o
d
p
,where s is the coefficient of x
0. This works by Proposition 3. Since forged shares are used in secret reconstruction, the interpolated polynomial f
′(x) will not be equal to the polynomial used by the dealer in share generation algorithm; therefore, a
i
′ ≠ a
i. Equation (31) will not work; thusz·r
−1 ≠s. Therefore, cheating is detected in PBLS.PBLS achieves the share size of|
v
i
| = |
s
| /ε such that ε > 0 is the probability for successful cheating. Theorem 38 provides the security of PBLS and a proof on the share size of PBLS [30–39].Theorem 38.
PBLS described in Section3.2.2 realizing the access structure Γ is ε-secure against up tot - 1 cheaters who may somehow know the secret beforehand. Moreover, the share size is |
v
i
|
=
p
2 = |
s
| /ε, where ε =1/p and v
i denotes the share space of thei-th participant U
i.Proof.
Sincep is prime, Z
p is a finite field. We let the secret to be p bits long so(32)
s
=
p
.
For successful cheating, an adversaryA has the sample space of p. Hence the probability is(33)
ε
=
1
p
.
Since every user receivesf(i) andy, the share is(34)
v
i
=
f
i
,
y
w
h
e
r
e
y
=
r
-
1
.
So|
f
(
i
)
| =p and |
y
| =p. Therefore,(35)
v
i
=
p
2
.
From Equations (32) and (33), (36)
s
p
=
ε
p
.
This implies that(37)
s
ε
=
p
2
.
From Equation (35)(38)
v
i
=
p
2
=
s
ε
.
Suppose an honest participantU
h having the share v
h
= (h,f(h) ) belongs to thek-th compartment. For a valid but incorrect secret s
′
∈ S to be accepted by U
h, after parsing another check polynomial g
′(x) with g
′(0) = s
′, the point (x
h,g(x
h)) should lie on the polynomial g
′(x). So, the successful cheating probability (PBLS, A) of cheaters A against PBLS is defined as(39)
ε
P
B
L
S
,
A
=
Pr
⁡
g
′
x
p
a
s
s
e
s
t
h
r
o
u
g
h
a
p
o
i
n
t
x
h
,
g
x
h
u
n
k
n
o
w
n
t
o
A
.
Since is a polynomialg(x) of degreet - 1 over F
p from different constant term, ε =1/p. This proves the theorem.Propositions35 and 36 indicate that PBLS is perfect since the secret can be recovered by the required threshold but not less. This is the same for Shamir’s scheme and Liu et al.’s scheme. Theorem 38 indicates that any cheating behavior can be detected, which is similar to Liu et al.’s scheme. Furthermore, PBLS and Liu et al.’s scheme have the same share size given to users. Therefore, PBLS and Liu et al.’s scheme have the same property of cheating detection.We now compare the security and properties of PBLS with Shamir’s scheme and Liu et al.’s scheme. Table1 shows that comparison of SPs and CO of these schemes.Table 1
Comparison of required properties for the schemes.
Scheme
Property
SP1
SP2
SP3
SP4
CO
Shamir’s scheme
√
√
√
X
1
Liu et al.’s scheme
√
√
√
√
2
PBLS
√
√
√
√
1
√: the property exists; X: the property does not exist.Table1 shows that the schemes have similar properties in terms of SP1, SP2, and SP3. However, Shamir’s scheme does not provide SP4. It also shows that PBLS achieves CO simultaneously. Even if PBLS provides good aspects in security and privacy, we need to mention that there is possibility that shareholders have some advantages over learning the secret since they have b as mentioned in Algorithm 28. So, our future research should focus on devising a new scheme to solve this probability.


## 4.2. Computation Analysis

In this subsection, we analyze the computation overhead of PBLS and give a comparison to Shamir’s scheme and Liu et al.’s scheme. Three operations are used in this analysis, which are modulo addition (add), modulo multiplication (mul), and modulo inverse (inv). The analysis will consider all the two algorithms. However Algorithm25 of basic scheme is not considered in this analysis since it is an initialization phase of PBLS.


### 4.2.1. Computations in PBLS

In PBLS, a share is computed from a polynomialf(x) of degreet - 1. Therefore, the polynomial has t terms andt - 1 of them are multiplied by a variable x. Each share requires modulo addition and modulo multiplication to be computed. Therefore, Table 2 shows computation in share generation of PBLS.Table 2
Computations in share generation of PBLS.
Share generation
Operation
mul
add
inv
Total
Number of operations
n(t -1)
nt
-
n(t -1) mul + nt addThe aim of secret reconstruction is to come up with a secret, which is done using Lagrange interpolation. A polynomial is interpolated usingt points, which are the shares and the identity of the user, i.e., (i, v
i). The polynomial f
′(x) is obtained as in Equation (27), which is rewritten as(40)
f
′
x
=
∑
i
=
1
t
v
i
·
p
i
x
,
w
h
e
r
e
p
i
x
=
∏
j
=
1
,
j
≠
i
t
x
-
x
j
x
i
-
x
j
.To compute eachp
i(x), Table 3 shows the computations in secret reconstruction of PBLS.Table 3
Computations in secret reconstruction of PBLS.
Secret reconstruction
Operation
mul
add
inv
Total
Number of operations
t
3 + t + 1
t
t
(t
3 + t + 1) mul + t add + t inv


### 4.2.2. Comparison

Now, we compare the computation overhead of PBLS with Shamir’s scheme and Liu et al.’s scheme. We follow the method done in Section4.2.1 to provide computation overhead comparison. Table 4 shows the computation overhead comparisons in share generation phase and secret reconstruction phase.Table 4
Computation overhead of related schemes.
Share generation
Scheme
Operation
mul
add
inv
Total
Liu et al.’s scheme
2n(t - 1)
2nt
-
2n(t - 1) mul + 2nt add
Shamir’s scheme
n(t - 1)
nt
-
n(t - 1) mul + nt add
PBLS
n(t - 1)
nt
-
n(t - 1) mul + nt add
Secret reconstruction
Scheme
Operation
mul
add
inv
Total
Liu et al.’s scheme
2(t
3 + t + 1)
2t
2t
2(t
3 + t + 1) mul + 2t add + 2t inv
Shamir’s scheme
t
3 + t + 1
t
t
(t
3 + t) mul + t add + t inv
PBLS
t
3 + t + 1
t
t
(t
3 + t + 1) mul + t add + t invResults in Table4 show that PBLS and Shamir’s scheme have the same computation overhead at share generation phase. The result is due to the use of a single polynomial when sharing and distributing the secret to users. However, comparing this result to Liu et al.’s scheme, the computation overhead is reduced by half in share generation phase. This indicates that PBLS has an efficient way to share the secret as compared to Liu et al.’s scheme but comparable with Shamir’s scheme.Considering secret reconstruction process, computation overhead on PBLS is higher by 1 mul as compared to Shamir’s scheme. This is so because of cheating detection in PBLS in which the operation is 1 mul but Shamir’s scheme does not have. However, results show that computation overhead of Liu et al.’s scheme at secret reconstruction still doubles as compared to PBLS. Therefore, PBLS is more efficient as compared to Liu et al.’s scheme in the concern of computation overhead.


## 4.2.1. Computations in PBLS

In PBLS, a share is computed from a polynomialf(x) of degreet - 1. Therefore, the polynomial has t terms andt - 1 of them are multiplied by a variable x. Each share requires modulo addition and modulo multiplication to be computed. Therefore, Table 2 shows computation in share generation of PBLS.Table 2
Computations in share generation of PBLS.
Share generation
Operation
mul
add
inv
Total
Number of operations
n(t -1)
nt
-
n(t -1) mul + nt addThe aim of secret reconstruction is to come up with a secret, which is done using Lagrange interpolation. A polynomial is interpolated usingt points, which are the shares and the identity of the user, i.e., (i, v
i). The polynomial f
′(x) is obtained as in Equation (27), which is rewritten as(40)
f
′
x
=
∑
i
=
1
t
v
i
·
p
i
x
,
w
h
e
r
e
p
i
x
=
∏
j
=
1
,
j
≠
i
t
x
-
x
j
x
i
-
x
j
.To compute eachp
i(x), Table 3 shows the computations in secret reconstruction of PBLS.Table 3
Computations in secret reconstruction of PBLS.
Secret reconstruction
Operation
mul
add
inv
Total
Number of operations
t
3 + t + 1
t
t
(t
3 + t + 1) mul + t add + t inv


## 4.2.2. Comparison

Now, we compare the computation overhead of PBLS with Shamir’s scheme and Liu et al.’s scheme. We follow the method done in Section4.2.1 to provide computation overhead comparison. Table 4 shows the computation overhead comparisons in share generation phase and secret reconstruction phase.Table 4
Computation overhead of related schemes.
Share generation
Scheme
Operation
mul
add
inv
Total
Liu et al.’s scheme
2n(t - 1)
2nt
-
2n(t - 1) mul + 2nt add
Shamir’s scheme
n(t - 1)
nt
-
n(t - 1) mul + nt add
PBLS
n(t - 1)
nt
-
n(t - 1) mul + nt add
Secret reconstruction
Scheme
Operation
mul
add
inv
Total
Liu et al.’s scheme
2(t
3 + t + 1)
2t
2t
2(t
3 + t + 1) mul + 2t add + 2t inv
Shamir’s scheme
t
3 + t + 1
t
t
(t
3 + t) mul + t add + t inv
PBLS
t
3 + t + 1
t
t
(t
3 + t + 1) mul + t add + t invResults in Table4 show that PBLS and Shamir’s scheme have the same computation overhead at share generation phase. The result is due to the use of a single polynomial when sharing and distributing the secret to users. However, comparing this result to Liu et al.’s scheme, the computation overhead is reduced by half in share generation phase. This indicates that PBLS has an efficient way to share the secret as compared to Liu et al.’s scheme but comparable with Shamir’s scheme.Considering secret reconstruction process, computation overhead on PBLS is higher by 1 mul as compared to Shamir’s scheme. This is so because of cheating detection in PBLS in which the operation is 1 mul but Shamir’s scheme does not have. However, results show that computation overhead of Liu et al.’s scheme at secret reconstruction still doubles as compared to PBLS. Therefore, PBLS is more efficient as compared to Liu et al.’s scheme in the concern of computation overhead.


## 5. Conclusion

In this paper, we proposed a new linear (t,n) threshold secret sharing scheme called PBLS, which is based not only on Shamir’s scheme but also on ElGamal cryptosystem. PBLS satisfies the required properties like security, recoverability, privacy, cheating detection, and share size. PBLS is (t,n) threshold scheme, which requires at least t shares to reconstruct the secret while any less than t should not be able to do it.Firstly, we draw the required features that secret sharing schemes satisfied by reviewing and analyzing some previous schemes like Shamir’s and Liu et al.’s. The required features drawn are security, recoverability of the secret, privacy of the secret, cheating detection of the forged shares presented for reconstruction of a secret and share size given to each user. We also reviewed some basic mathematical and cryptographic concepts, which assisted in designing methods for cheating detection such as finite fields and ElGamal cryptosystem.Based on the withdrawn required features of secret sharing schemes, basic scheme and PBLS were designed. Basic scheme aims at hiding the secret, which is the initialization of PBLS. The secret is revealed during cheating detection. This is an idea of ElGamal who developed a cryptosystem that can hide a message using field elements. PBLS apples Shamir’s secret sharing scheme to share the secret. Polynomialf(x) is used in share generation phase such that the coefficient of x is the element hiding the secret. Secret reconstruction was done by interpolating a polynomial using Lagrange interpolation. Cheating detection was achieved by multiplying the coefficient of x of the polynomialf(x) by multiplicative inverse of r to reveal the secret f
′(0).After the design of PBLS, an analysis was made, which was presented in two ways. These were security analysis and privacy analysis with required features and computational overhead analysis. It was determined that the security with privacy of PBLS was similar to Liu et al.’s scheme. However, in terms of cheating, Shamir’s scheme proved to be weak. Cheating detection was attained in both PBLS and Liu et al.’s schemes even though PBLS used only one polynomial. Furthermore, the required features like recoverability were analyzed to be similar to Liu et al.’s scheme. Computational analysis showed that number of operations in PBLS is almost equal to the computations in Shamir’s scheme, which is half of Liu et al.’s scheme. This analysis made PBLS to be a better scheme in terms of efficiency than Liu et al.’s scheme and in terms of security than Shamir’s scheme.



---

*Source: 5134534-2019-08-04.xml*