Verifiable Social Multi-Secret Sharing Secure in Active Adversarial Model

1 Introduction

The concept of secret sharing (SS) was introduced independently in 1979 by Shamir [1] and Blakley [2]. In an SS scheme, a dealer shares a secret among a set of participants in such a way that while later the secret can be recovered from the shares corresponding to each authorized subset of participants, non authorized subsets obtain no information about the secret from their shares. The set of authorized subsets is called the access structure of the scheme. (t, n)-threshold secret sharing (denoted for short as (t, n)-TSS) is the most theoretically studied and practically applied type of secret sharing in which the access structure consists of those subsets containing at least t players out of a total of n players. It should be noted that both of the original secret sharing schemes were (t, n)-TSS. Ordinary TSS schemes are able to share only one secret during each execution. However, many SS applications, such as those associated with key-management, require the protection of more than one secret. Executing SS schemes multiple times to separately share each of the secrets is the trivial solution to this problem, but in this case each participant should store a lot of information securely. In order to circumvent this issue, multi-SS (MSS) schemes are introduced in the literature. There are many different definitions for MSS. Here, we consider the following definition introduced by Jackson et al. [3] which is used also in several constructions ([4–10]).
A multi-secret sharing (MSS) scheme is a method to share more than one secret among a group of participants in such a way that: any authorized subset of participants is able to recover all the secrets,

(1)any non-authorized subset of participants obtains no information about any of the secrets.

If these conditions are met, but the knowledge on some of the secrets enables the participants in a non-authorized subset to recover information on other secrets, the scheme would be called a weakly secure MSS scheme. Otherwise, we have a strongly secure MSS scheme.

Existing MSS schemes can be classified into two categories: multistage SS schemes and single-stage MSS schemes. In the case of multistage SS, secrets can be recovered in different stages without jeopardizing the security of the uncovered secrets [11–15]. Compared to the multistage SS schemes, single-stage MSS (which is the focus of this research and will be denoted hereafter only by MSS) schemes are more efficient. In this type of MSS, all the secrets will be recovered at once. A practical MSS scheme proposed in 2000 by Chien et al. [16] by using systematic block codes and matrices. Another practical MSS scheme is proposed in 2004 by Yang et al. [17] based on Shamir’s SS scheme. In the above-mentioned schemes, the dealer and participants can provide fake shares to other players. To prevent the participants and the dealer from cheating, verifiable MSS (VMSS) schemes can be used [18]. There is also a generic construction to convert any SS scheme to an MSS scheme using cellular automata in [19]. However, the complexity of this conversion is quadratic in the number of the secrets. Therefore, this approach is not practical in all settings.

Some issues can be considered in all of the above-mentioned (M)SS schemes:

(1)The shared secret is only secure against the static adversaries, i.e., those who can not get access to the shares corresponding to an authorized subset of participants in the secret’s lifetime. However, some secrets with long lifetime require to be secure against mobile adversaries that over time can get access to the shares corresponding to subsets of participants of their choices.

(2)During reconstruction of the secret, all participants have the same level of authority. This is not a realistic assumption and it should be possible to assign different authorities to participants due to the difference in their reputations or other participants’ trusts in them.

(3)Participants’ authorities are fixed over time. Again, this is not a realistic assumption and participants’ authorities can change over time due to the changes in their reputations or other participants’ trusts in them.

To solve the first problem, the notion of proactive secret sharing (PSS) is introduced by Herzberg et al. in [20]. To the best of our knowledge, there exist only a few PSS scheme in the literature [20–24]. However, none of them can be used to share multiple secrets simultaneously. As the solution to the second problem, multipartite secret sharing schemes can be used in which there exists different ways to provide different authorities. The interested readers may refer to [25–31] for examples of some multipartite SS schemes. Almost all of these schemes can be easily extended to an MSS variant (by using the same ideas used in ordinary TSS). There are also some researches that tried to propose more efficient multipartite MSS schemes [4, 32, 33].

To solve the last problem, the concept of social secret sharing (SSS) is introduced in [34] by Nojoumian et al. The authors of [34] also proposed two constructions for SSS schemes with unconditional security. Their first scheme provides security in the presence of passive adversaries who try to obtain information about the secret by eavesdropping. Their second scheme withstands adversaries who can actively interfere with the scheme, as opposed to just observing and analyzing. In [35], Eslami et al. employed hierarchical threshold secret sharing and proposed another social secret sharing scheme with unconditional security in passive adversarial model.

1.1Our Contribution

Unfortunately, none of the existing SSS schemes can be used for simultaneous sharing of multiple secrets. This is in fact due to the fact that here, the shares need to be updated proactively. To fill this gap, the aim of this paper is to apply symmetric encryption to Nojoumian et al.’s SSS scheme and obtain a social MSS (SMSS) scheme. However, the problem is not as trivial as it seems and naive application of symmetric encryption would result in an inefficient SMSS scheme. That is because Nojoumian et al.’s SSS scheme is unconditionally secure and its unconditional security is obtained at the cost of some communication and computational overheads. However, computational security is the best that can be achieved when we are dealing with threshold MSS [36, 37] or multi-use symmetric encryption concepts. Therefore, here is a list of our contribution to solve this problem:

-We propose the first construction of a social secret sharing scheme for sharing multiple secrets (i.e., SMSS) by exploiting symmetric encryption methods as well as Feldman’s commitment scheme [38] together with

Nojoumian et al.’s idea.

-Our share renewal process improves that of Nojoumian et al.’s scheme in terms of the communication costs.

-We prove that our scheme achieves strong security in the presence of a mobile active adversary.

-We provide comparisons to show the efficiency of our SMSS scheme.

1.2Organization of the paper

The rest of the paper is organized as follows: in Section 2, the preliminaries needed in the rest of the paper are reviewed. The notion of social multi-secret sharing and the proposed scheme are presented in Section 3. Section 4 analyzes the security and efficiency of the proposed scheme. Finally, the concluding remarks are provided in Section 5.

2Preliminaries

In this section, the concepts of social secret sharing and symmetric encryption are reviewed.

2.1Social Secret Sharing

A social secret sharing scheme is defined by three algorithms; “sharing” (Sha), “social tuning” (Tun) and “reconstruction” (Rec) algorithms. In Sha, the dealer shares a secret among a group of participants with different authorities and then leaves the scheme. Tun is periodically performed after the sharing phase. Its aim is to adjust the participants’ authorities based on their behaviors (cooperation/availability) over time using a trust function [39]. Newcomers are always able to join the scheme and receive shares of the secret through this algorithm. There would be no necessity for the presence of the dealer and authorized subsets of participants can execute Tun without revealing the secret. When all participants in an authorized subset decide to reconstruct the secret, the Rec algorithm is executed to recover the secret. For further clarification and details of social secret sharing, the interested reader is referred to [34].

2.2Symmetric Encryption

A symmetric encryption scheme is a set of three polynomial-time algorithms (Gen, Enc, Dec) such that Gen takes a security parameter α in unary and returns a secret key k; Enc takes a key k and a message m and returns a ciphertext c; Dec takes a key k and a ciphertext c and returns m if k was the key under which c was produced.

There are many definitions for the security of a symmetric encryption scheme. In this paper, the following security definition is required (Note that it may not be adequate for a symmetric encryption scheme to be considered secure, but it is sufficient for our goal).

A symmetric encryption scheme is secure against known plaintext attack (KPA) (and would be called KPA- secure) if, there exists no polynomial-time adversary able to obtain any information about the plaintext that corresponds to a randomly generated ciphertext even by accessing one or more pairs of plaintext/ciphertext encrypted under the same key.

3The Proposed Social Multi-Secret Sharing Scheme

In this section, first, the notion of social secret sharing is extended to social multi-secret sharing (SMSS). Then, by using symmetric encryption schemes, Nojoumian et al.’s SSS scheme and Feldman’s VSS scheme, we construct an efficient SMSS scheme.

3.1Social Multi-Secret Sharing

An SMSS scheme is a social secret sharing scheme in which the simultaneous sharing of multiple secrets is possible. The same as an SSS scheme, an SMSS scheme is defined by three algorithms; “sharing” (Sha), “social tuning” (Tun) and “reconstruction” (Rec) algorithms. The definitions of all the algorithms are as before except that the input of Sha and the output of Rec algorithms are both a set of secrets. For the security, the definition of strongly secure MSS scheme (explained in Section 1) is considered here.

3.2Notations

We use the following notations to describe the scheme.

U : the set of participants, t: the threshold parameter, n: number of participants, Pi: the ith participant,

wi: the weight assigned to Pi, m: number of secrets,

Si: the ith secret,

Π: a KPA-secure symmetric encryption scheme,

sk: the secret key,

ci: the ith ciphertext,

shij : the jth share of Pi,

shij→kl: the lth sub-share of Pk obtained from Pi’s jth share.

3.3The Proposed Scheme

To the best of our knowledge, none of the existing approaches used to obtain MSS schemes (except for the one of [19]) are applicable when the participants’ shares required to be updated proactively. The only applicable solution is to use the idea of [19] to convert existing SSS schemes to SMSS schemes. However, the computational overhead of this approach is quadratic in the number of the secrets and therefore, it is not efficient. Our motivation here is to apply symmetric encryption to Nojoumian et al.’s SSS scheme and obtain an efficient SMSS scheme. The same as all existing threshold MSSS, our scheme achieves computational security.

q
Let U = {P1, P2, · · · , Pn} be the set of n participants and let {S1, S2, · · · , Sm} ⊂ Zm denote a set of m secrets where q denotes a large prime number. Assume Π = (Gen, Enc, Dec) is a KPA-secure symmetric encryption scheme.

In the sharing algorithm of the proposed scheme, at first, the dealer runs the Gen algorithm of the cryptosystem Π to generate a secret key sk. Then, he uses the Enc algorithm of Π with sk as the secret key to encrypt the set of secrets and obtains a set of m ciphertexts. Finally, he shares sk among participants using the sharing algorithm of Feldman’s VSS scheme [38]. During Tun, at first, players’ reputation values are renewed based on their behaviors in the past time interval. Then, using the new reputation values, the assigned weight to each participant and his shares would be updated. If an authorized subset of participants decides to reconstruct the secrets, the Rec algorithm of the proposed scheme is run in which, first the secret key sk is reconstructed. Then, using the Dec algorithm of the cryptosystem Π, the recovered secret key sk and the set of ciphertexts, the original secrets will be recovered.

We now provide the details of sharing, tuning and reconstruction algorithms in the following sections.

3.3.1Secret Sharing (Sha) Algorithm

In this algorithm, the dealer performs the following steps:

(1)Runs the Gen algorithm of Π to get a secret key sk.

(2)Runs the Enc algorithm of Π with sk as the secret key m times, each time with one of the secrets Si(1 ≤ i ≤ m) as the plaintext to obtain a set of m ciphertexts: {c1 = Enc(S1, sk), c2 = Enc(S2, sk), · · · , cm = Enc(Sm, sk)}.

(3)Publishes the set of ciphertexts {c1, c2, · · · , ck }.

(4)Constructs the polynomial f (x) = a0 + a1x + · · · + at−1xt−1 with a0 = sk and randomly chosen ai from

Zq for (1 ≤ i ≤ t − 1).

(5)Computes and publishes the values Ai = gai (mod q) for i = 0, · · · , t − 1.

(6)Let ωi (i = 1, · · · , n) denote the weight assigned to Pi according to his initial reputation value. Then, for each participant Pi:

(a)For j = 1, · · · , ωi: computes shij = f (xij ) where xij = iω − ω + j and ω << t is the maximum weight that any participant can have.

(b)Sends {shi1, · · · , shiωi } as Pi’s share from the set of secrets to him via a secure channel.
(7)

j=1
Each participant Pi verifies the validity of his shares {shij }ωi

Each participant Pi verifies the validity of his shares {shij }ωi

through the following relation:

1
t−

gshij = Y A ij
k

x

k (mod q), (1)

k=0

where xij = iω − ω + j and broadcasts (xij, shij ) as a complaint against the dealer if Equation (1) does not hold.

(8)If the number of complaints is at least equal to t then, all participants output reject and stop execution of the protocol.

(9)The dealer reveals the share (shij ) corresponding to each complaining participant Pi.

(10)Each participant checks the validity of the revealed shares by the dealer through Equation (1) and outputs

reject if any of the revealed shares fails this equation. Otherwise, outputs accept.

3.3.2Social Tuning (Tun) Algorithm

When the set os secrets are shared, Tun can be executed many times. There is no need for the dealer to be online and participants can execute this algorithm by themselves. The aim of this algorithm is to enhance the authority of reliable and cooperative players by increasing their weights and reduce the authority of unreliable participants due to their past behaviors by decreasing their weights. In this algorithm, at first, participants’ new reputation values are computed by a trust function such as that used in [34]. Then, based on these new values, the participants’ new weights will be calculated and the shares corresponding to each participant will be renewed cooperatively by participants. Let Arbsub denote an arbitrary subset of participants and define

WIndex = {(i, j)|Pi ∈ Arbsub&j = 1, · · · , ωi}. The details of this algorithm are as follows:

(1)The players, updates the reputation value and the weight assigned to each member of U by using a trust function such as that used in [34].

(2)Each player Pi ∈ Arbsub, for j = 1, · · · , ωi:

(a)Generates a polynomial f [ij](x) = b[ij] + b[ij]x + b[ij]x2 + · · · + b[ij] xt−1 over Zq where b[ij] = shij ,

and b[ij]

[ij]

0 1 2

t−1 0

1 , · · · , bt−1 are randomly chosen values from Zq .

(b)Computes B[ij] = gb[ij] for k = 1, · · · , t − 1 and publishes these values.

k k

(c)

k
Let ω′

Let ω′

denote the new weight assigned to each participant Pk ∈ U according to his new trust value.

k
Then, for each Pk ∈ U and l = 1, · · · , ω′

computes shij→kl = f [ij](xkl) as the sub-share from his

j-th old share corresponding to the l-th new share of Pk and sends these values to him via a secure

channel.

(3)Upon receiving his sub-shares from the set of participants executing Tun, each player Pk ∈ U computes the

k
value B[ij] = Qt−1 Ax[ij]

0 k=0

k (mod q) for each of his received sub-shares (shij→lm). Then, checks the validity

of each of his sub-shares through the following relation:

t−1 v

v
gshij→kl = Y B[ij]xkl (mod q), (2)

v=0

k
where i and j is such that Pi ∈ Arbsub and Pk ∈ U , respectively, j = 1, · · · , ωi, and l = 1, · · · , ω′ . Pk

broadcasts (ij, kl) as a complaint if the equation does not hold for shij→kl.

(4)The participants remove (i, j) from WIndex if there is at least t different complaints against j-th polynomial of Pi (i.e., t complaints with (ij, ∗∗) form).

(5)Each Pi ∈ U , for each j = 1, · · · , ωi, publishes the value shij→kl corresponding to each broadcasted

complaint.

(6)Participants check the validity of the published value using Equation (2) and remove (i, j) from WIndex

if it does not hold for at least one of the published values from j-th polynomial of Pi.

(7)Let |WIndex| denote the size of the set WIndex. Then, if |WIndex| ≥ t, each player Pk ∈ U erases his old shares from the set of secrets and computes his new shares as shkl = Pi:(i,∗)∈W Index Pj:(i,j)∈W Index shij→kllij (0)

l
for l = 1, · · · , ω′ where ∗ denotes an arbitrary index and lij (·) denotes the corresponding Lagrange polyno- mial to the pair (i, j) from WIndex.

(8)

k k k i:(i,∗)∈W Index j:(i,j)∈W Index k
Each player P ∈ U updates the public values A for k = 1, · · · , t−1 as A = Q Q B[ij]lij (0).

Each player P ∈ U updates the public values A for k = 1, · · · , t−1 as A = Q Q B[ij]lij (0).

3.3.3Reconstruction (Rec) Algorithm

Let assume that Arbsub be an arbitrary subset of participants. Then, a trusted party (called the share combiner) can perform the following steps to reconstruct the set of secrets:

(1)Checks the validity of each of the provided shares through the following relation:

t−1

gshij = Y Axij
k

k (mod p), (3)

k=0

where i is such that Pi ∈ Arbsub and j = 1, · · · , ωi.

(2)If the number of valid shares (those for which the above equation holds) is at least equal to t, uses Lagrange

interpolation method to compute the secret key sk.

(3)Reconstructs the set of original secrets as {S1 = Dec(c1, sk), S2 = Dec(c2, sk), · · · , Sm = Dec(cm, sk)}.

4Security and Performance Analysis

In this section, we first prove that the proposed SMSS scheme achieves computational security in the presence of active mobile adversaries. Then, the proposed scheme is compared with the only existing SSS scheme secure against active mobile adversaries (i.e., Nojoumian et al.’s second scheme) in terms of communication complexity, computational complexity, the share size, the number of public parameters, and the achieved security and features.

4.1Security Analysis

In this section, we prove that our proposed SMSS scheme is strongly secure under active mobile adversary model. In order to do so, we first state the following lemmas which prove that Sha, Tun and Rec algorithms of the proposed scheme are computationally secure under an active adversary model.

Lemma 1. The Tun algorithm of the proposed scheme is computationally secure, i.e., non-authorized subsets of participants obtain no information about the secret key sk from their shares through this algorithm.

Proof. The Tun algorithm of the proposed SMSS scheme can be considered as follows. At first, each participant distributes his shares by using Feldman’s VSS scheme. Then, participants erase their old shares and compute their new shares as a linear combination of the received shares from all the participants executing this algorithm. The computational security of Feldman’s VSS scheme makes it computationally infeasible for non-authorized subsets of participants to obtain information about the old shares of participants executing this algorithm. Therefore, the only information that the adversary has access to is the set of shares corresponding to a non- authorized subset of participants from different time intervals. Since the shares from different time intervals are obtained from different polynomials, they can not be used together to obtain information on the secret key sk. Therefore, this algorithm does not give any advantage to the adversary compared to what he has from the Sha and Rec algorithms.

Lemma 2. In the proposed scheme, no non-authorized subset of participants can obtain information about the secret key sk that is used to encrypt the set of original secrets.

Proof. In the proposed scheme, a KPA-secure encryption scheme is used to encrypt the set of original secrets. KPA-security of the used cryptosystem makes it computationally impossible for a polynomially bounded ad- versary to obtain information about the the secret key sk from the set of ciphertexts c1, · · · , cm. Without

obtaining any information from the ciphertexts, using the shares is the only remaining way in which the adver-
sary can obtain information on the secret. In the following, it is shown that obtaining information about the secret is computationally infeasible assuming that an adversary can gain access to shares of only non-authorized subsets of participants in each time interval. The Sha and Rec algorithms of the proposed scheme are exactly the same as those in Feldman’s VSS scheme which indicates that these algorithms of the proposed scheme are computationally secure. The Tun algorithm is what makes the proposed scheme different from Feldman’s scheme and its computational security is shown in Lemma 1. Security of all the three algorithms indicates the computational security of sk in the proposed scheme.

Table 1. Comparisons Between SMSSS and SSSS with n as the Number of Participants, t as the Threshold Parameter and m as the Number of Secrets in the Proposed Scheme.

Scheme

SSSS

SMSSS

Computational complexity (# of Mu operations)

Sha

Tun Rec

Each participant The dealer

Each participant

The share combiner

O(nt3)

O(nt2) O(n2t4) O(t4)

O(t2)

O(m + nt2) O(nt3) O(m + t2)

Sha

2

1

Communication complexity

Tun

3

1

Rec

1

1

The share size

O(t2|q|)

O(t|q|)

Achieved security level

Unconditional

Computational

Multi-secret sharing

No

Yes

# of public parameters

0

O(t2)

Theorem 1. The proposed social multi-secret sharing scheme is strongly secure under active mobile adversary model.

Proof. Assume that m−1 of the secrets shared by the proposed scheme are revealed in clear (note that the worst case is considered) and Sm is the only secret about which no information is known. At first, note that Lemma 2 states that it is computationally infeasible for non-authorized subsets of participants to obtain information about the secret key sk. Now, KPA-security of the used cryptosystem makes it computationally impossible for
a polynomially bounded adversary to obtain information about other ciphertexts (e.g., cm) by using the known (plaintext, ciphertext) pairs. Therefore, it can be concluded that the proposed scheme is strongly secure in the active mobile adversary model.

4.2Comparison

In this section, the proposed scheme (denoted here by SMSSS) is compared with Nojoumian et al.’s second scheme (denoted by SSSS) which, the same as the proposed scheme is secure under active mobile adversary model. The comparisons is done in terms of communication and computational complexity, the share size, the number of public parameters, the security provided by each of the schemes and the properties that each of the schemes achieve. The results of the comparisons are summarized in Table 1.

4.2.1Communication Complexity

In this section, the number of communication rounds required in each algorithm of the schemes is compared:

•The Sha algorithm: This algorithm of SSSS requires two communication rounds, one for the share distribution by the dealer and another one for the pairwise verification of shares between participants. SMSSS requires one communication round in the Sha algorithm. Note that no communication is needed for the share verification in SMSSS.

•The Tun algorithm: This algorithm of SSSS requires three communication rounds (one round in phase I of its Tun algorithm and two more communication rounds in phase II of that algorithm, please see [34]).

SMSSS requires one communication round in the Tun algorithm in which the share of each participant is transferred to him.

•The Rec algorithm: Both of the schemes requires one communication round in their Rec algorithm to

send the shares to the share combiner.

Based on these statements, it can be concluded that SMSSS outperforms SSSS in terms of the communication complexity. The results are summarized in Table 1.

4.2.2Computational Complexity

Let n denote the maximum number of parties who can join the scheme and let t be the threshold parameter of the schemes; note that n > t. Also, let w (for the sake of simplicity we assign w = t) be the maximum weight of each player in the schemes. Let Mu, E n, De, and E x denote a multiplication, a symmetric encryption, a

symmetric decryption, and an exponentiation operation, respectively. The operations E n, De and E x can be

done by performing some fixed number of Mu operations. Therefore, the number of operations E n, De and E x can be approximated by c1Mu, c2Mu, c3Mu for some constants c1, c2 and c3, respectively. In the following, an approximate computational comparison between the SMSSS and SSSS is brought.

In Sha algorithm of SMSSS, at first, the dealer needs to encrypt m messages. This process can be done by m E n operations. Then, he should compute the shares that correspond to each participant Pi ∈ U . Each share generation can be done via evaluation of a (t − 1)-th degree polynomial on a random input which can be done by O(t) Mu operations. Therefore, generating the shares corresponding to Pi can be done by ωit Mu operations. Hence, the overall complexity of this process is O(nt2)Mu operations. Finally, the dealer should perform t exponentiations to generate the required public values for verification. Therefore, the overall computations that the dealer needs to perform is O(m + t2n)Mu operations. Moreover, in Sha algorithm of SMSSS, each participant Pi ∈ U needs to verify the validity of each of the received shares. Each share verification requires t Mu and t E x operations. Therefore, the overall computations needed to be done by each participant in Sha algorithm of SMSSS can be approximated as O(t2) Mu operations. To generate each share, in SSSS, the dealer computes a univariate polynomial of degree t − 1 as a share by computing the value of a bivariate polynomial of degree t − 1 at a point with fixed first coordinate. This can be done by (t − 1) Mu operations. Therefore, generating the shares corresponding to Pi can be done by ωit Mu operations. Hence, the overall complexity of this process is O(nt2)Mu operations. To verify the validity of each received share in SSSS, each participant, for each of the received shares does a pairwise checking with all the shares of all participants (including himself). Each pairwise checking is done by computing the value of a polynomial of degree t − 1 at a point. As explained earlier this

i=1
process can be done in O(t) Mu operations. The number of pairwise checking for each share is Pn

ωi − 1.

Therefore, the overall computations that is required to be done by each participant to verify the validity of all of his received shares is O(nt3) Mu operations.

In Tun algorithm of SMSSS, each participant, as a dealer, shares each one of his old shares. Moreover, the participants need to verify the validity of their received shares. Based on the computations done in the previous paragraph, the computations needed to be done by each of the participants in this algorithm is O(nt3) Mu

operations. Phase II of SSSS is computationally more complex than phase I of their algorithm. That is because

the verifications are done in the second phase. In this phase, each participant for each of his shares acts as a dealer and shares the value zero among the participants. Using the notations brought at the beginning of this section, to accomplish this goal, the computations that is needed to be carried out by each participant is O(nt3)

Mu operations. Moreover, the participants require to verify the validity of their received shares by pairwise checking. To do this process, each participant needs to carry out O(n2t4) Mu operations. Therefore, the overall computations that is needed to be done by each participant in Tun algorithm of SSSS is O(n2t4) Mu operations.

In the Rec algorithm of SMSSS, the share combiner needs to verify the validity of the provided shares and then reconstruct the secret key sk using lagrange interpolation method. Finally, he uses the secret key sk to decrypt the set of ciphertexts. Based on the computational complexity of the share verification of SMSSS, that of

Lagrange interpolation method and decryption operations, the overall computations that is needed to be done by the share combiner in this algorithm of SMSSS is O(t2 + m) Mu operations. In the Rec algorithm of SSSS, same as in SMSSS, at first, the share combiner needs to verify the validity of the received shares by pairwise checking

for each two of the received shares. Then, he needs to reconstruct the secret using the Lagrange interpolation method. Therefore, the overall computations that is needed to be done by the share combiner in Rec algorithm of SSSS is O(t4) Mu operations.

Based on the achieved computational complexities, it can be concluded that the proposed scheme (which is able to share multiple secrets) outperforms Nojoumian et al.’s scheme in terms of computational complexity (which is able to share only one secret).

4.2.3The Share Size

t

4.2.4Security

While SSSS is unconditionally secure under active mobile adversary model, SMSSS is computationally secure in the same model. Therefore, SSSS guarantees a more strong security definition.

4.2.5Achieved Properties

SSSS is a verifiable social secret sharing scheme which can only share one secret during each execution of it. SMSSS, while preserving all the properties achieved by SSSS, is a multi-secret sharing scheme.

4.2.6Public Parameters

In Sha algorithm of SMSSS, in order to make the participants capable of verifying the validity of their shares, the dealer publishes t public values from Zq . Moreover, in the Tun algorithm of SMSSS, each participant Pi needs to publish ωi(t − 1) public values. Therefore, the maximum number of public parameters in SMSSS is

O(t2). Note that in SMSSS, after each execution of Tun, the number of public values would be reduced to t.

Since SSSS achieves the verifiability property by using bivariate symmetric polynomials, it does not require to publish any public parameters. Therefore, Nojoumian et al.’s scheme outperforms the proposed one in terms of the number of public parameters.

5Conclusion

In this paper, the concept of social secret sharing (SSS) is generalized to social multi-secret sharing (SMSS). Then, by combining a modified version of Nojoumian et al.’s SSS scheme and symmetric encryption schemes, a construction for SMSS scheme is proposed. Afterward, it is proved that the proposed scheme is strongly secure in active adversarial model. Finally, the efficiency of the proposed scheme is demonstrated by comparing it with the only existing SSS scheme with provable security in active adversarial model.