Space Efficient Computational Multi-Secret

Sharing and Its Applications

Aggelos Kiayias1 , Murat Osmanoglu2 , Alexander Russell3 , and Qiang Tang4

1
University of Edinburgh, UK
[email protected]
2
Ankara University, Turkey
[email protected]
3
University of Connecticut, USA
[email protected]
4
New Jersey Institute of Technology, USA
[email protected]

Abstract. In a (t1 , . . . , t` )-multi-secret sharing scheme (MSSS), ` inde-

pendent secrets s1 , . . . , s` are shared with n parties in such a way that at
least ti parties are required to recover the secret si (while si remains hid-
den with fewer shares). We consider the problem of minimizing the share
size of MSSS in the challenging setting when there are many secrets to
be shared among many parties. To circumvent the information-theoretic
lower bound (e.g., Blundo [4]), we focus on the computational setting.
A simple generalization of computational secret sharing (Krawczyk [17])
to multi-secret sharing yields a scheme with share size/overhead scaling
linearly in `, the total number of secrets.
To beat this linear scaling, we consider constructing MSSS based on a
related notion of encryption—dynamic threshold public key encryption
(DTPKE)—that enables a sender to dynamically specify a threshold for
each ciphertext. None of the existing DTPKE is well-suited for our pur-
pose. Thus, we propose a new construction of a dynamic threshold public
key encryption scheme with improved efficiency characteristics. We then
give a recursive application of our construction that yields an efficient
MSSS with share size only logarithmic in the number of secrets (thus
effectively O(log `) as in the common cases, where `, n are polynomially
related).
Finally, we describe an application of our space efficient (1, 2, . . . , n − 1)-
MSSS to a special tool called gradual verifiable secret sharing which is the
fundamental building block for general multiparty computation (MPC)
with n players that provides fairness without honest majority.

1 Introduction

Many cryptographic systems rely on a trusted authority that maintains and

employs a secret to carry out basic tasks such as encryption, decryption, or key
generation. Reliance on a single authority, however, raises immediate security
and reliability concerns. Secret sharing is the classical cryptographic primitive
that can be used to overcome these obstacles. Given a set of n parties and a
collection A of subsets of the parties, a secret sharing scheme for A is a method
of distributing shares of a secret among the parties so that any subset of parties
from A can reconstruct the secret, but any subset of parties which is not in A
cannot. Such schemes were introduced and studied by Blakley [3] and Shamir [25]
for threshold structures: in such “threshold schemes,” any subset of the parties
can recover the secret precisely when the cardinality of that particular subset
is above a certain threshold. Ito et al. [21] later generalized the notion to more
general access structures.
A fundamental efficiency concern for secret sharing schemes is the size of the
share that must be distributed to each participant. Karnin [16] showed that in
any unconditionally secure secret sharing scheme, the length of each share must
be at least that of the secret. To achieve better efficiency, Krawczyk [17] relaxed
the security guarantee by introducing a natural computational notion: while t
shares can be used to efficiently recover the secret, any fewer than t give “no
information” (in a precise sense) about the secret to a computationally bounded
adversary. This permits striking improvements in share size: each share has size
(m/t + λ) instead of m, where m is the size of the shared secret and λ is the
security parameter.
An important and well-studied variant arises when multiple secrets must be
distributed with different thresholds to the parties [1,4,26,27]; such schemes are
known as multi-secret sharing schemes (MSSS). Jackson et al. [15] considered
the most natural case—called multi-secret threshold schemes—in which each
secret si is associated with a threshold ti , and only more than ti participants
can recover si from their shares. Blundo et al. [4] established that in order to
achieve unconditional security for multi-secret threshold schemes, the size of
the share that each participant holds must be, at least, linear in the number
of secrets. These lower bounds have been complemented by more recent work
in the unconditional setting: Masucci [22] presented a weaker notion of security
for multi-secret sharing schemes in unconditional settings, and gave some lower
bounds for the size of the shares of each participant. Herranz et al. [12] then
proved that the size of the share for each participant in multi-secret threshold
schemes must indeed be linear in the number of secrets, even if the scheme enjoys
only the weaker unconditional security introduced by [22].
Motivated by Krawczyk’s success in the single secret case, computationally
secure MSSSs can be considered for improved efficiency [12]. However, straight-
forward application of Krawczyk’s scheme [17] for a MSSS still incurs a linear (in
the number of secrets) size share for each player: e.g., in [12], ` instances of [17]
are run and the resulting share size is m(1/t1 + · · · + 1/t` ) + `λ (if there are `
secrets, and λ denotes the security parameter, and m denotes the shared secret
size). The first term is clearly unavoidable; however, the second term yields an
overhead that grows linearly in the number of secrets. In many applications, the
number of shares can be very large. This raises our central question:

Is there a computationally-secure multi-secret sharing scheme providing share

size that grows sub-linearly with the number of shares?

2
 In this paper, we answer this question in the affirmative: we give a new MSSS
construction that achieves overhead that scales only logarithmically in `. Aside
from their intrinsic interest, we remark that such efficient MSSSs that do not
rely on an external public storage (see below for more elaborations).

The interesting cases when both `, n are poly(λ). For multi-secret sharing,
there are two simple cases; the total number of user n is small (however large is
the number of shares `), or the total number of shares ` is small. In the first case,
it follows that the range of all different thresholds would be small (smaller than
n). It is easy to see that we can simply group secrets with the same threshold into
one bigger secret chunk, and run the trivial application of Krawczyk’s scheme
[17] on the chunks, which yields an MSSS with each share size overhead at most
nλ for a very small n. Similarly, we can directly apply the Krawczyk’s scheme
[17] for the latter case, and the resulting `λ overhead is fine now as ` is small.
For many of the interesting cases, the number of shares and number of parties
are both significantly large. In particular, we will consider a general setting where
both n, ` are poly(λ). For example, in our multiparty computation application,
we will need to consider a (1, 2, 3, . . . , n)-MSSS (here ` = n). We are aiming to
achieve an asymptotically small overhead for each share size (O(log `) · λ). And
note that in this case, O(log n) is the same as O(log `), thus sometimes in the
paper, we used n, ` interchangeably for measuring space efficiency.

Regarding a public bulletin board. As a counterpoint to our results, Her-

ranz et al. [12] observe that in the computational setting one can “shift” private
storage to public storage via encryption. In particular, an information theoretic
MSSS can be used to generate the shares first, which are then encrypted and
stored on a public bulletin board. Thus, each player must only store a short key
locally and retrieve all other material from the bulletin board. In this paper, we
focus on constructing a space efficient MSSS without relying a public “bulletin
board”. There are a couple of obvious reasons that motivate us: reducing trust
for space efficient MSSS scheme (without needing an online party who faith-
fully holds all the data). Moreover, sometimes such public bulletin board service
may be impreferable or even unavailable as in case of common deployment of
secure multiparty computation or decentralized applications. We remark, also,
that even though we focused on the setting without a bulletin board, our tech-
niques can actually provide efficiency savings also in the setting of having a
public bulletin board. In particular, treating public storage as outsourced stor-
age associated with each player, existing schemes use as much storage as in the
information theoretic case (O(m · `) for each player at least [12]), while applying
our technique achieves O(m · log `) for each player. See the efficiency discussion
in section 4.2 for more details. 5
5
One may wonder whether simply applying the tool of information dispersal (IDS)
on the data stored in the public bulletin board solves the problem, However, doing
so is highly non-trivial. As we will show later, in order to make the IDS effective, we
first need to carefully design the scheme so that the public bulletin board size scales
only linear with each threshold, not always ` as in [12].

3
1.1 Our Results

We present a new construction for threshold MSSS (in this paper, we focus
entirely on threshold MSSSs, so we drop the adjective “threshold”) that achieves
share size O(m(1/t1 +· · ·+1/t` )+log `·λ) which is nearly optimal for large `. 6 As
the first term is inherent for carrying the information of the message, the second
term is the overhead that we try to minimize. Concretely, our contributions are
as follows:

Construction of space efficient computational multi-secret sharing. We

begin with a generic construction, providing the basic relationship between MSSS
and DTPKE, and then focus on efficient constructions of DTPKEs. In more
detail:

A generic construction. To warm up, we first point out a generic construction

for computational MSSS. Inspired by [17], we use an encryption scheme as a
building block. To capture the various threshold requirements, we rely on a
dynamic threshold public key encryption scheme (DTPKE) [6]. Intuitively, given
the secrets (s1 , .., s` ), we apply a DTPKE scheme to encrypt each secret si with
its threshold ti ; thus, the resulting ciphertext ci requires at least ti users in
order to be decrypted. Then, following [17], we apply an efficient information
dispersal scheme (IDS) [17, 23] to distribute the ciphertexts together with all
the public keys among users in a way that ti users can construct ci from their
shares. This yields a generic construction that transforms a DTPKE scheme
into an MSSS. The resulting construction is computationally secure if the given
DTPKE is semantically secure. This simple construction enables us to focus on
the challenge of designing an efficient DTPKE.

A new dynamic threshold public key encryption scheme. The generic construc-
tion is useful only when it is applied to an efficient instantiation of DTPKE, and
obtaining such a scheme appears to be challenging. The only existing construc-
tion that offers a constant-size ciphertext for DTPKE is given by [6] (without
this property the encryption itself already precludes the possibility of our effi-
ciency target). However, the scheme requires O(n) public group elements, called
the combining key, and all elements in the combining key are used even for
decrypting a ciphertext with the threshold 1 (here n is the number of users).
This immediately prevents the above reduction from yielding an efficient MSSS.
Requiring some kind of combining key seems to be unavoidable in the construc-
tion of DTPKE with small ciphertexts and, moreover, this particular inefficiency
appears to be an inherent aspect of the existing system.
6
Note that there are three possible scenarios for an MSSS: few secrets to be shared
that can easily be realized using an efficient single secret sharing scheme, few people
to share the secrets for which the information dispersal algorithms will not be useful
since the threshold values are small, and many secrets to be shared among many
users that we consider in this work.

4
 Taking all these facts into consideration, we propose a new DTPKE scheme
that has an allowed threshold range in the parameters. We then show how to
apply a degree reduction technique on the exponent that can be tuned to the
threshold range to yield our new construction. The result is a combining key that
scales linearly only in the size of the threshold range rather than the number
of users n.7 Specially, for a particular threshold range [t, 2t), if the combining
keys are distributed using an information dispersal scheme for the threshold t,
then the size of the share will be constant. Moreover, the structure of our new
scheme is algebraically simpler than the original scheme of [6]. These features
enable us to recursively apply our general construction to get an efficient MSSS.
Finally, we remark that the basic technical structure of this new DTPKE is
rather different from the one in [6] which might be of independent interest.

A space efficient construction of MSSS. Direct application of our new DTPKE

still cannot give us an efficient MSSS. As we emphasized above, we need to
distribute all combining keys among the participants. Evenmore, since all com-
ponents of the combining key are required in decrypting even a ciphertext with
threshold 1, all combining keys should be given to each participant. It is clear
that, even with our new construction, applying our general reduction naively
results in a linear size share for each participant.
To circumvent this obstacle, we divide the threshold range into log n parts:
∆1 , . . . , ∆log n , where ∆u = [2u−1 , 2u ) (w.l.o.g, we assume n is a power of 2). We
then run independent DTPKE instances together with an IDS for each threshold
range ∆u in order to share the secrets {si | ti ∈ ∆u }. For each window ∆u , there
are at most 2u elements for the combining key, while the minimum threshold
for this range is 2u−1 . Thus we can now apply the information dispersal scheme
[17,23] to efficiently distribute the combining key; thus each share has size O(1).
Since both n, ` are poly(λ), the final share size is O(log `), where ` is the number
of secrets.

Applications to fair MPC with smaller private state. We show an inter-

esting application of our MSSS to get an efficient building block for MPC pro-
tocol that guarantees fairness when there is no honest majority. Hirt et al. [13]
introduced a primitive called gradual verifiable secret sharing as the main build-
ing blockPof an MPC protocol that first splits a secret s into n − 1 pieces si ,
n−1
i.e., s = i=1 si , and then jointly reveals si using a secret sharing scheme with
threshold i one by one. Thus, the secret sharing scheme prevents the adversary
who aborts the protocol to learn the output. This primitive, in our terminology,
is a (1, 2, . . . , n − 1)-MSSS in which the shares are reconstructed one by one.
Instantiating this primitive using our efficient MSSS scheme, yields an MPC
protocol satisfies fairness with each party having only O(log n · λ) storage for the
gradual VSS part, while [13] only achieves linear size O(nλ).
7
Note that this change of having an allowed range is a strict generalization of the
previous definition of DTPKE rather then a weakening. To see this, we can simply
set the allowed range to be [1, n] to instantiate the previous schemes, e.g., [6].

5
Paper overview. We recall the basic definitions and security requirements
in Section 2. To establish the basic relationship between MSSS and DTPKE,
we propose a generic construction for the computational MSSS in Section 3. In
Section 4, we first present a new construction of DTPKE since non of the existing
construction is well-suited for our purpose, then we propose an efficient MSSS
that employs the new construction of DTPKE. We also show an application of
our efficient MSSS to secure multi-party computation in Section 5.

2 Preliminaries
Notations: Let ` denote the number of secrets to be shared and n denote the
number of users, which will also be the upper bound for the threshold values.
We use (s1 , ..., s` ) to denote the secrets to be shared, and the letter t to denote
threshold values, i.e. each ti is associated with the secret si . The letter m is used
to denote the size of the secret. We let λ denote the security parameter.

2.1 Definitions
In this section, we give some definitions and the security requirements of the
multi-secret threshold schemes.

Definition 1. A (t1 , . . . , t` )-multi-secret threshold sharing scheme is defined by

two protocols as follows:
– Share: This protocol takes the security parameter λ, the set of n players P,
the global secret →
−
s = (s1 , ..., s` ) to be shared, and ` threshold values (t1 , ..., t` )
where ti ∈ [n]. It outputs the set of shares {shi }Pi ∈P .
– Reconstruct: This is a protocol executed among a subset of users: each user
i takes the index j ∈ [`] and his secret share shj as input, and they jointly
output the corresponding secret sj or ⊥.

Remark. We assume that the share protocol also outputs some public parameters
required for the reconstruction protocol (such as description of the underlying
group system). For simplicity, we consider these as part of share for each user.
A multi-secret sharing scheme has to satisfy the following two properties:

Correctness: Enough shares are able to reconstruct the secret. Formally, if S =

⊆ {shi }Pi ∈P where Share(λ, P, →
−
tj
{shik }k=1 s , {ti }) = ({shi }Pi ∈P ), then
j t
sj ← Reconstruct(j, {shik }k=1 ).

However, if |S| < tj , then Reconstruct(j, S) = ⊥.

Security: We define the computational security of a multi-secret threshold shar-
ing scheme similar to the regular security notion of semantic security that is
used in encryption schemes. Consider the following game between a challenger
C and an adversary A.

6
 – The challenger gives the set P of users and the thresholds values (t1 , ..., t` )
to the adversary.
– The adversary A submits the challenge threshold ti .
– The adversary also submits two global secrets → −
s (0) , →
− (0) (1)
s (1) where si 6= si
(0) (1)
and sj = sj , ∀j 6= i.
For simplicity, we just require the adversary to submit two global secrets
→
−s (0) , →
−
s (1) such that they differ only at the index i. It can be easily seen to
imply the general case.
– The challenger chooses a random bit b ∈ {0, 1}, runs the share protocol
({shk }Pk ∈P , params) ← Share(→
−
s (b) , P, {tk }, λ), and gives ({shk }k<ti , params)
to the adversary.
– Finally, A outputs a guess b0 .

The advantage of the adversary in breaking the security of the scheme is

determined as
AdvMSSS
A = | Pr[b0 = b] − 1/2|.
We say that the scheme is computationally secure if AdvMSSS
A is negligible.
We require, also, the notion of an information dispersal scheme, defined be-
low.
Definition 2 (Rabin [23]). A (t, n)-information dispersal scheme is a protocol
that distributes a file F among n parties in such a way that the recovery of the
file is possible in the presence of up to (n − t) failed (inactive) parties at the time
of reconstruction.
Information dispersal is very like secret sharing without the security require-
ment. Indeed, the file is transformed into n “shares” with the property that any
t can entirely reconstruct the file. The major parameter of interest is the size
of the “shares.” The protocol given by [23] achieves optimal share size of length
|F |/t + O(1).

2.2 Multi-Sequence of Exponents Diffie-Hellman Assumption

We here set down the cryptographic assumption—essentially identical to the
assumption used in [6]—on which the security of our new construction for the
dynamic threshold public key encryption is based.

Definition 3. Let G1 , G1 , and GT be three groups of prime order p. We say a

map e : G1 × G2 → GT is a bilinear map if it satisfies the following properties:
– Bilinearity. For all a, b ∈ Zp , g1 ∈ G1 , and g2 ∈ G2 ; e(g1a , g2b ) = e(g1 , g2 )ab ,
– Non-degeneracy. If g1 and g2 are generators for G1 , G2 , respectively, then
e(g1 , g2 ) is a generator for GT ,
– Efficiency. There exists an efficient algorithm [8] to compute g, h 7→ e(g, h)
for elements g, h ∈ G.

7
 A bilinear map group system is a tuple B = (p, G1 , G2 , GT , e) that consists of
elements as described above.

Definition 4. The decisional problem (`, n, t)-MSE-DDH is defined as follows:

let B = (p, G1 , G2 , GT , e) be a bilinear group systems, and `, n, and t be three
integers. Let g0 be a generator of G1 and h0 be a generator of G2 . Given two
random coprime polynomials f and g, of respective orders ` and t, with the roots
y1 , . . . , y` and x1 , . . . , xt respectively, where xi 6= yj , and several sequences of
exponentiations
`+n−1
k.γ.f (γ)
g0 , g0γ , . . . , g0γ , g0 ,
`+n−1
g0α , g0α.γ , . . . , g0α.γ ,
n−1
h0 , hγ0 , . . . , h0γ ,
n−1
α.γ α.γ k.g(γ)
hα
0 , h0 , . . . , h0 , h0

and also T ∈ GT , decide whether T is equal to e(g0 , h0 )k.f (γ) or some random
element of GT where k, α, γ ∈ Zp∗ .

Delerablee et al. [6] justified the intractability of the decisional problem

(`, n, t)-MSE-DDH in the generic group model. As they point out, it is non-
interactive and falsifiable.

3 Generic Construction of Computational Multi-Secret

Sharing Schemes
To circumvent the lower bound restriction in the perfect secret sharing scheme
[16], Krawczyk [17] proposed a computational (t, n)-secret sharing for one se-
cret. Specifically, after encrypting the secret, the ciphertext is distributed via an
information dispersal scheme to the users, while a regular Shamir secret sharing
scheme is applied to distribute the secret key. It can achieve essentially optimal
share size: m/t, where m is the size of the data to be shared and t is the threshold
value. As a secret key is only λ bits long, the final share size for each user is only
m/t + λ. This elegant framework inspires us to consider the efficiency benefits of
a computational notion of security in the setting of multi-secret sharing as well.
A natural way to generalize Krawczyk’s idea to multi-secret sharing (assum-
ing there are ` independent secrets to share) is to run the Krawczyk scheme `
times. Briefly, each secret can be encrypted under a different key. Then, the re-
sulting ciphertexts will be dispersed as in [17], and ` independent Shamir secret
sharing schemesPare then carried out P`to distribute the secret keys. Thus, the to-
`
tal size will be i=1 (mi /ti + λ) = i=1 mi /ti + `λ. This strategy was observed
in [11] and analyzed there in detail. As discussed in the introduction, our goal in
this paper is to construct a multi-secret sharing scheme with at most sub-linear
overhead in the number of secrets. Furthermore, we adopt a model where there
is no available public bulletin board.

8
 The above strategy inherently requires overhead linear in `, as each secret
and key are treated independently. We need to deviate from this natural con-
struction and generalize Krawczyk’s idea in a fashion that meaningfully combines
information across secrets. To realize this plan, we apply a generalized version of
(threshold) encryption scheme so that the ciphertext can be created with flexible
thresholds while each user has only a single secret key.
We first give the formal definition of such a dynamic threshold public key en-
cryption (DTPKE), and describe a generic construction of MSSS using DTPKE
as a building block. This generic construction will serve as the stepping stone
for us to achieve an efficient MSSS.

3.1 Dynamic threshold public key encryption

The notion of dynamic threshold public key encryption (DTPKE) can be consid-
ered as a refinement of the regular threshold encryption scheme. In a DTPKE,
each user/receiver has a secret key, and a sender can specify a threshold t so that
the ciphertext requires t secret keys to jointly recover the plaintext. Moreover,
the choice of the threshold t is not fixed in advance—it can be determined during
encryption by the sender. We present here a simplified definition which will be
enough for our use in this paper. In more detail, a DTPKE is composed with
the following algorithms:

– D.Setup(λ): This algorithm takes a security parameter λ as input, and

generates a master secret key M K, an encryption key EK, and a combining
key CK. It then outputs the public parameters params = (EK, CK), and
gives M K to the registration authority.
– D.KeyGen(M K, i): This algorithm takes M K as input, and outputs the
user’s secret key uski and the user’s public key upki for each user i.
– D.Enc(EK, t, m): This algorithm takes the encryption key EK, a threshold
t, and a message M as inputs. It then outputs a ciphertext C.
– D.ShareDecrypt(uski , C): It takes the user’s secret key uski and a cipher-
text C as inputs, and outputs a decryption share σi .
– D.Combine(CK, T, σ1 , ..., σt , C): The algorithm takes the combining key
CK, a ciphertext C, a subset T of t user public keys, and a list (σ1 , ..., σt )
of t decryption shares as inputs. It either outputs a message M or ⊥.

Note that Delerablee et al. [6] included two more algorithms ValidateCT
and VerifyShare as parts of usual DTPKE scheme. Since those algorithms
are not essential for our purpose, and can easily be obtained using traditional
techniques, we omit them here.

Correctness: The correctness of a dynamic threshold public key encryption scheme

requires that for any ciphertext C = D.Enc(EK, t, M ) with a threshold t, if t
users correctly produced the partial decryption shares σi , then the Combine
algorithm on the set {σ1 , ..., σt } correctly outputs the message M . Formally,

Pr[D.Combine(CK, T, {σi }i∈[t] , C) = M ] = 1

9
if C = D.Enc(EK, t, M ), and ∀i ∈ [t], σi = D.ShareDecrypt(uski , C).

Security: We here give the security requirements of the primitive. Briefly, the se-
mantic security of the scheme guarantees that fewer than t users cannot decrypt
a ciphertext with the threshold t. Even if we allow an adversary to corrupt t − 1
users, we claim that the content of the ciphertext with the threshold t will still
be semantically secure. Consider the following game between a P.P.T adversary
A and a challenger C:
– The adversary A submits a threshold t.
– The challenger simulates the Setup algorithm and gets the system pa-
rameters (M K, CK, EK). It then gives the public parameters params =
(EK, CK) to the adversary.
– A is allowed to make corrupt queries. To respond the queries, the challenger
runs D.KeyGen to get secret key-public key pairs and sends the corre-
sponding keys (upk1 , usk1 ), . . . , (upkq , uskq ) to A.
– A submits two messages M0 and M1 with the threshold t. The challenger
randomly chooses b ∈ {0, 1}, and sends Cb as an encryption of Mb to A.
– A can adaptively make extra q 0 corrupt queries.
– Finally, A outputs a guess b0 and wins the game if b0 = b.
We require in the above game that q + q 0 < t. The advantage of A is defined
as  
Advcpa Pr[b0 = b] − 1  .
 
A =  2
We say a dynamic threshold public key encryption scheme is semantically secure
if for any polynomial time adversary A the advantage Advcpa A is a negligible
function of λ.
Remark. The adversary can also make “ShareDecrypt” queries, and get some
decryption shares of a ciphertext for some particular users. However, the “Cor-
rupt” queries give more advantages in comparison to ShareDecrypt queries, and
even we allow the adversary to corrupt up to t users in proving the security of
the ciphertext with the threshold t. Thus, allowing only corrupt queries would
be enough for the security definition.

3.2 Constructing MSSS from DTPKE.

We now show how to use the DTPKE to construct a MSSS that provides compu-
tational security. Note that this generic construction itself does not give efficiency
guarantee, but it will be a critical component in the final construction. It will
also allow us to treat the security analysis in a modular fashion.
First, consider an intermediate case where there exists a public bulletin board
through which all data can be accessed by any user. Assume there are ` secrets
s1 , ..., s` to be shared with corresponding thresholds t1 , ..., t` . These secrets can
simply be encrypted using the DTPKE with the corresponding thresholds, and
the resulting ciphertexts—along with the combining keys—can be placed on the

10
bulletin board. In addition, each user is given a secret key as a share. To recon-
struct the secret si , ti users jointly decrypt the corresponding ciphertext and
get the plaintext as the secret si . To construct an actual MSSS and remove the
reliance on a bulletin board, we need to further distribute the bulletin board
data among users. The ciphertexts can be distributed via an information disper-
sal scheme (IDS) without affecting the security. But all the combining keys are
required to be able to decrypt even a ciphertext with the threshold 1. Thus, all
of them should be given to each user.
Formally, given an information dispersal algorithm IDS, and a DTPKE scheme
D=(D.Setup, D.KeyGen, D.Enc, D.ShareDecrypt, D.Combine), a multi-
secret threshold sharing scheme can be obtained as follows:
Share: The algorithm takes the security parameter λ, the set of users P =
{1, . . . , n}, the secrets s1 , ..., sl to be distributed, and the threshold values
{ti }i∈[`] . It first calls D.Setup(λ) to get the parameters (M K, EK, CK).
It then runs D.KeyGen to get the secret keys and the public keys
{(upkj , uskj )}j=1,...,n
for the users.
The algorithm then encrypts each secret and computes ci = D.Enc(EK, ti , si )
for the secrets si using its threshold ti .
Next, the algorithm distributes each ci by running an IDS on it using thresh-
old ti . Suppose the shares are {ci,j }i∈[`],j∈[n] .
This algorithm ends with each user j receiving his key pair (uskj , upkj ), the
combining key CK, and ` shares (c1,j , ..., c`,j ) for ciphertexts.
Reconstruct: Assume there is a set S of users that jointly run the protocol
in order to get the corresponding secret sk , and each user holds a share
(uskj , upkj , CK, {ci,j }) where j ∈ S, i ∈ [`], and |S| ≥ tk . They first
jointly reconstruct ck using the IDS reconstruct algorithm on the shares
{ck,j }j∈S . Then each user in the set S runs D.ShareDecrypt on ck to
get a decryption share σk,j . Finally, they jointly compute the secret as
sk = D.Combine({σk,j }, ck , CK).

Remark. Regarding efficiency, the size of each user’s share will be |CK| + |usk| +
Pl
|upk| + i=1 |ci,j |. In order to guarantee sub-linear size share, we need to ensure
the ciphertext size to be small. Furthermore, we demand a dynamic threshold
encryption scheme such that either (i) the combining key of the scheme is con-
stant or (ii) the structure of the scheme enables us to employ IDS on CK such
that each share size of CK will be at most sub-linear.

Correctness. According to the IDS property, when |S| ≥ tk , the ciphertext ck

can be recovered. Thus, following the correctness of the underlying DTPKE, |S|
secret keys together with the combing key can jointly decrypt ck , and get the
corresponding secret sk .

Security. The security of the generic MSSS construction follows from the seman-
tic security of the DTPKE scheme. Formally,

11
Theorem 1. If D is a semantically secure DTPKE scheme, then the construc-
tion given above is a computationally secure MSSS.

Proof. Assume there is an adversary that breaks the security of the multi-secret
threshold scheme; then we can build an algorithm B that breaks the security of
the scheme D. Consider the following game between the algorithm B and the
adversary A.

– B submits the set of users P and ` threshold values (t1 , . . . , t` ).

– A submits the threshold ti∗ and two global secrets →−s (0) , → −s (1) where →
−
s (0)
→
−
and s (1) ∗
differ only at the index i .
– The algorithm B invokes the challenger of the scheme D in order to get the
public parameters (EK, CK).
B then makes corrupt queries for any q users, and gets q secret key-public
key pairs {uskj , upkj }qj=1 from the challenger.
(0) (1)
B gives two secrets si∗ and si∗ together with the threshold value ti∗ to the
(b) (b)
challenger, and receives the challenge ciphertext ci∗ of the secret si∗ .
B makes extra corrupt queries for any q 0 more users and gets q 0 secret key-
0
public key pairs {uskj , upkj }q+q 0
j=q+1 where q + q = ti∗ − 1.
(0)
B also computes the ciphertexts ci of the secrets si for all i 6= i∗ ∈ [`]. It
then produces the shares {ci,j }i∈[`],Pj ∈P for the ciphertexts

(b)
(c1 , . . . , ci∗ −1 , ci∗ , ci∗ +1 , . . . , cl )

by running IDS protocol.

Finally, B gives all (ti∗ − 1) shares {(uskjk , upkjk , CK, ci,jk )}i∈[`],k<ti∗ to the
adversary.
– The adversary A submits a guess b0 . The algorithm B gives this guess b0 to
(b)
the challenger of DTPKE as a guess for the challenge ciphertext ci∗ .
M SSS
Assume AdvA is the advantage of A in breaking the security of the
construction, and AdvBDT P KE is the advantage of S in breaking the security of
M SSS
DTPKE. Since A’ s view will be identical to a real attack, if AdvA > , then
DT P KE
AdvB ≥ . Thus, we don’t have any security loss.

3.3 Obstacles to efficient DTPKE

Conventional threshold encryption schemes insist on a fixed threshold deter-

mined when the system is initialized, e.g., [25]. It is not clear how to advanta-
geously apply such a scheme in the MSSS case, as each threshold would—at least
naively—require its own scheme. So, we consider the DTPKE schemes in which
the threshold is not fixed during setup, i.e., the scheme allows one to dynam-
ically set a threshold for each ciphertext. To the best of our knowledge, there
is only one construction for DTPKE [6]. Unfortunately, it has a constant size
ciphertexts but calls for a large combining key (linear in the number of users),

12
so that we cannot directly use it for an efficient MSSS. Let us first recall the
construction of [6] to approach the challenge of providing an efficient DTPKE.
The construction employs an arbitrary bilinear map group system. Let e :
G1 × G2 → GT be a bilinear map, and g and h be two randomly selected
generators for the groups G1 ,G2 , respectively. In the scheme, the encryption key
i
EK consists of (2n + 2) group elements (u, v, {hα.γ }2n−1 i=0 , D) where u = g
α.γ
,
v = e(g, h) , and D consists of (n − 1) random integers (d1 , ..., dn−1 ) from Zp ;8
α
n−2
and the combining key consists of (n − 1) group elements (h, hγ , ..., hγ ) and
1
D. The secret key of user j is g γ+j .
The encryption algorithm computes the header and the session key for a
threshold t of users as (Hdr = (C1 = u−k , C2 = hkαP (γ) ), K = v k )
n
Y Y
P (γ) = (γ + x) · (γ + x) ,
x=1 x∈D1

where D1 ⊂ D, and |D1 | = t − 1. Note that for a threshold t, the algorithm

adds (t − 1) dummy users to fix the degree of the polynomial P (γ) as (n +
t − 1). Since the decryption procedure applies bilinear maps to C2 and usk, a
collection of t secret keys can be used collectively to reduce the degree of P (γ)
by t as they will have t different (γ + xi ) in the denominator of the exponent.9
i
Thus, the combining key {hγ }n−2 i=0 will be enough to complete the decryption
of the ciphertext. However, with fewer than t secret keys, the polynomial in
the exponent of e(g, h) must have degree no smaller than n. In this case, the
combining key will not be sufficient to complete the decryption of the given
n
ciphertext since it is impossible to reconstruct e(g, h)γ . This works for any t,
which is the core idea allowing a dynamic threshold.
In the above construction, all the (n − 2) group elements of the combining
key must be used in the decryption process, even if the threshold value t of the
ciphertext was set as 1. This fact creates an efficiency problem when one utilizes
this DTPKE to instantiate our generic construction (of a MSSS) since all the
(n − 2) group elements of the combining key must be given to each user. Using
information dispersal to distribute the combining key (as it is public information
anyway) can alleviate this problem when the threshold is very large. However,
this idea fails for small thresholds. Furthermore, reliance on the full combining
key appears to be inherent in the construction strategy.

4 Main Construction
In this section, we will give our main construction of MSSS with nearly optimal
share size. We first propose a new construction of DTPKE for a given threshold
8
D forms a set of dummy users, which will be combined with the set of users in order
to be consistent with the threshold values.
9
The decryption procedure uses a special aggregate technique, which employs a simple
fact that a product of inverses of coprime polynomials can be written as a sum of
inverses of affine polynomials. For the detailed description, we refer the paper [6].

13
range [δ0 , δ1 ) which is more efficient than that of [6] in the sense that the combin-
ing (and encryption) key grows linearly only in the range of the threshold values
rather than the total number of users. Such a DTPKE scheme has an important
property in our context: for threshold range [δ0 , 2δ0 ), if one distributes combin-
ing keys via an IDS using threshold δ0 , then each share size will be constant. We
then show how our generic construction can be adapted to exploit this efficiency
property of the new DTPKE to get our actual space efficient multi-secret sharing
scheme.10

4.1 New construction of DTPKE

As described in Sect. 3.3, the construction of [6] requires a linearly-size (in total
number of users n) “combining key,” which prevents the scheme from yielding
an efficient MSSS. We here propose a new construction for DTPKE so that the
combining (and encryption) key grows linearly in the range of the threshold t.
The new scheme enables senders to specify an arbitrary threshold for the cipher-
text in a given range [δ0 , δ1 ), and—as in [6]— achieves optimal size ciphertexts
(a constant number of group elements). Additionally, our scheme is algebraically
simpler than the original scheme of [6].
In more detail, the new scheme creates the secret key of a user i as usk =
g P (γ) where P (γ) is the evaluation of a (δ1 − 1)-degree polynomial P (x) at
a secret point γ. For a random k, α, the encryption algorithm of the scheme
encodes the evaluation of a (t − δ0 )-degree polynomial A(x) into C2 = hkαA(γ)
as a part of ciphertext. During the decryption, each user pairs a secret key with
the ciphertext C2 in order to form a decryption share e(g, h)kαA(γ)P (γ) which
will have the evaluation of a (δ1 − δ0 + t − 1)-degree polynomial at the secret
point γ in the exponent. The essential point for correctness here is to remove the
dependence between the decryption share and the threshold t in the exponent.
We observe that using simple linear algebra, t users can find t coefficients to
remove (t − 1) higher terms of P (x)A(x), arriving at a polynomial with degree
(δ1 − δ0 ). With one more small trick, we can bring it down to δ1 − δ0 − 1. Thus,
the combining key containing (δ1 − δ0 − 1) corresponding powers will be enough
to complete the decryption. Security will follow because when there is a deficit
in the number of decryption shares, then there will necessarily be a leftover term
in the exponent that masks the session key. Formally, given a threshold interval
[δ0 , δ1 ), our DTPKE is as follows:

– Setup: The algorithm first chooses parameters defining a bilinear map sys-
tem for a given security parameter λ: B = (p, G1 , G2 , GT , e) where e : G1 ×
G2 → GT is a bilinear map and |p| = λ. The algorithm then randomly chooses
two integers γ, α ∈ Zp∗ , and two generators g ∈ G1 and h ∈ G2 . It also ran-
domly selects (δ1 − δ0 − 1) integers xi ∈ Zp∗ . The algorithm then outputs the
10
Note that giving a construction for a specific threshold range is a generalization of
the previous DTPKE. If the range can be simply defined as [1, n], our new scheme
implies the regular DTPKE given by [6].

14
 master secret key msk = (g, α, γ), the encryption key
 i

δ1 −δ0 −1 δ1 −δ0 −1
EK = u, v, {hα.γ }i=0 , {xi }i=1

where u = g α.γ and v = e(g, h)α , and the combining key

 i

δ1 −δ0 −1 δ1 −δ0 −1
CK = {hγ }i=0 , {xi }i=1 .

– KeyGen:(i, msk) The algorithm takes the master secret key msk as input.
It assigns an integer i ∈ Zp∗ to each user as his upk, and constructs the
(δ1 − 1)-degree polynomial Pi (x) = iδ1 −1 xδ1 −1 + · · · + i2 x2 + ix + 1. It then
outputs the user’s key pairs as usk = g Pi (γ) and upk = i for all users.
– Enc(t, δ0 , δ1 , EK, M ): The algorithm takes as input the encryption key EK,
a threshold value t ∈ [δ0 , δ1 ), and a message M . It randomly chooses an
integer k ∈ Zp∗ and calculates the ciphertext C = (C1 , C2 , C3 ) as

C1 = u−k , C2 = hkαA(γ) , C3 = K · M,
where the polynomial A(x) = (x + x1 ) . . . (x + xt−δ0 ) and K = v k is used as
a session key. Since A(·) is (t − δ0 )-degree polynomial, and t ∈ [δ0 , δ1 ), the
second component C2 = hkαA(γ) of the ciphertext can be computed from
EK (see the explanation below).
– ShareDecrypt(uski , C): The algorithm takes a ciphertext (C1 , C2 , C3 ) and
secret key of a user as inputs. It computes the decryption share as
σi = e(uski , C2 ) = e(g, h)k.α·Pi (γ)·A(γ) .
– Combine(CK, {σi }), {upki }): This algorithm takes the set of decryption
shares {σ1 , . . . , σt } and the identities {1, . . . , t} as inputs (w.l.o.g, we assume
that the shares are from users 1, . . . , t, and the Pi (·) are defined using the
coefficients h1, i, i2 . . . , iδ1 −1 i for i ∈ [t]).
It first finds t values a1 , . . . , at , (not all zero) that satisfy
t
X
ai Pi (x) = Q(x) ,
i=1

where Q(x) is (δ1 − t)-degree polynomial.11 This can be done by finding a

nontrivial solution to the following linear system:
1 2δ1 −1 · · · tδ1 −1
     
a1 0
1 2δ1 −2 · · · tδ1 −2  a2  0
..  ×  ..  =  ..  (1)
     
 .. .. ..
. . . .   .  .
1 2δ1 −t+1 · · · tδ1 −t+1 at 0
11
Note that a1 , . . . , at are also applied to calculate the value H = t−δ
Q 0 P
i=1 xi ( ai ),
which is used in the denominator in the decryption. P Thus, not to get zero in the
denominator, a1 , . . . , at must be chosen such that ai · =
6 0

15
 (Observe that the system has t unknowns and t − 1 constraints; hence the
nullspace has dimension at least 1.) It follows that:
t
Y Pt
(σiai ) = e(g, h)k.α·A(γ)· i=1 ai P i(γ)
,
i=1

and it is equal to e(g, h)kα·Q(γ)A(γ) for a (δ1 −δ0 )-degree polynomial Q(x)A(x).
We further define:
t−δ
Y0 X 
Q(x) · A(x) − H
R(x) = , where H = xi ai .
x i=1

In one formula, the combine algorithm then extracts the key as:
t
Y
K = [e(C1 , hR(γ) ) σiai ]1/H
i=1
−kαγ R(γ)
= [e(g ,h )e(g, h)kαQ(γ)·A(γ) ]1/H
kα[Q(γ)A(γ)−γR(γ)]/H
= e(g, h)
= e(g, h)kα

(All the above value can be computed from public values; see the details
below about correctness.)
Finally, it outputs C3 /K as the plaintext.

Efficiency: We can see that the construction has secret key and ciphertext both
given by a constant number of group elements; the encryption key and combining
key size grow linearly in the size of the range where the thresholds fall.

Correctness: Note that all the coefficients of the polynomial A(x) are public
and A(x) is with degree t − δ0 < δ1 − δ0 , thus the ciphertext C2 = (hαA(λ) )k is
δ1 −δ0 −1
computable from the public values hα , hαγ , . . . , hαγ contained in EK.
Furthermore, since the degree the coefficients of the polynomials {Pi (x)} are
all public, the equations for the linear system can easily be formed. Observe
that the coefficient matrix of the linear system has rank (t − 1) and there are t
unknowns for the equations. Thus, there are always a solution set for a1 , . . . , at .
More importantly,
P since the solution set of the linear system aims at reducing the
degree of i ai Pi (x), i.e., to kill the higher degree terms, the resulting polynomial
Q(x) will have degree [δ1 − 1 − (t − 1)] = δ1 − t.
Finally, the polynomial R(x) is equal to
t−δ
Y0
Q(x) · A(x) − H X 
, where H= xi ai
x i=1

is the constant term of Q(x)A(x). Thus, R(x) will have degree δ1 − δ0 − 1, and
all the coefficients are known (or defined by the values of ha1 , . . . , at i). It follows

16
 δ1 −δ0 −1
that hR(γ) can be computed from the public values h, hγ , . . . , hγ that are
contained in the combining key.
Security: We first briefly explain the intuition for the security. In the KeyGen
algorithm, the rows of the Vandermonde matrix are used as the coefficients for
generating the polynomial Pi (x) in the secret keys. So, if we remove any column
from the coefficient matrix of the linear system, the resulting matrix will be
a Vandermonde matrix which has full rank. Thus, the system (1) with (t − 1)
equations will have only one solution, in which all ai are zero. However, the
system (1) with at most (t − 1) equations and t coefficients will have many
solutions.
P Thus, when t < δ1 , using one such solution in which not all ai are zero
and ai · = 6 0, t users can decrease the degree on the exponent of the decryption
shares by at most t − 1. If the ciphertext is assigned threshold t0 > t, then the
leftover degree (on the exponent hiding K) will be larger than δ1 − δ0 . Thus,
the combining key will not be enough to compute the leftover term, and finish
the decryption. (Otherwise, the adversary can reduce degrees on the exponent
which violates the underlying assumption.)
Theorem 2. The dynamic threshold public key encryption scheme given above
is IND-CPA secure under MSE-DDH assumption.
Proof. Assume there is an adversary A that breaks the security of DTPKE, then
we claim that we build a simulator S that breaks the security of the assumption
MSE-DDH. Both the adversary and the simulator are given the threshold interval
[δ0 , δ1 ) and a threshold value t. The simulator S interacts with the adversary A
as follows:
– The simulator is given a group system B = (p, G1 , G2 , GT , e) and an MSE-
DDH instance in B. Thus, the simulator has two coprime polynomials f and
g with the degree (t − δ0 ), and with their distinct roots y1 , . . . , y(t−δ0 ) and
z1 , . . . , z(t−δ0 ) . S has also a sequence of exponentiations
δ1 +t−δ0 −1
k.γ.f (γ)
g0 , g0γ , . . . , g0γ , g0 ,
α.γ δ1 +t−δ0 +1
g0α , g0α.γ , . . . , g0 ,
δ1 −δ0 −1
h0 , hγ0 , . . . , h0γ ,
2.δ1 −2.δ0 +1
α.γ α.γ k.g(γ)
hα
0 , h0 , . . . , h0 , h0

as well as T ∈ GT which is either equal to e(g0 , h0 )k.f (γ) or some random

element of GT .
– To produce the public parameters, S first sets
f (γ) α.γ.f (γ)
g = g0 , u = g0 = g α.γ
h = h0 , v = e(g0 , h0 )α.f (γ) = e(g, h)α .

Since f is (t − δ0 )-degree polynomial, u and v can be calculated from the

given instance.

17
 δ1 −δ0 −1
The simulator S then forms the set {xi }i=1 as follows: it sets the first
(t−δ0 ) elements as xi = zi where z1 , . . . , zt−δ0 are the roots of the polynomial
g; and the remaining elements xt−δ0 +1 , . . . , xδ1 −δ0 −1 are chosen as random
integers in Zp∗ . Finally, it gives the encryption key
i
δ1 −δ0 −1 δ1 −δ0 −1
EK = (u, v, {hα.γ }i=0 , {xi }i=1 )

and the combining key

i
δ1 −δ0 −1 δ1 −δ0 −1
CK = ({hγ }i=0 , {xi }i=1 )

to the adversary.
– When the adversary makes a corrupt query for a user with the identity id, the
simulator first picks a random integer i ∈ [n], and gives the corresponding
secret key uski = g Pi (γ) and public key upki = i to the adversary. Note
that since Pi (x) = iδ1 −1 .xδ1 −1 + · · · + i2 .x2 + i.x + 1 is an (δ1 − 1)-degree
f (γ).Pi (γ)
polynomial, the secret key uski = g0 can be computed from the given
instance.

– The adversary submits two messages M0 , M1 . The simulator chooses a bit

b ∈ {0, 1}, and sets the ciphertext Cb = (C1 , C2 , C3 ) as
−k.γ.f (γ) k.g(γ)
Cb = (g0 , h0 , T · Mb )

and returns Cb to A. It can be easily proved that if we set k 0 = k/α, then

0 0
C1 = u−k , C2 = hk .α.g(γ) .
0 0
Note that if T = e(g0 , h0 )k.f (γ) , then C3 = v k .Mb , and C2 = hk .α.g(γ) =
0
hk .α.A(γ) as in the original scheme.
– The adversary outputs a guess b0 and the simulator gives b0 to the challenger.

Assume AdvDTA
P KE
is the advantage of A in breaking the security of the
construction, and AdvMS
SE−DDH
is the advantage of S in breaking the security
of the assumption. If T = e(g0 , h0 )k.f (γ) , then A’ s view will be identical to a
real attack. Thus AdvDT
A
P KE
= | Pr[b0 = b] − 1/2| > . However, if T is just
random group element, then Pr[b0 = b] = 1/2. Therefore
1 1
AdvM
S
SE−DDH
≥| ±  − |= .
2 2

4.2 Computational multi-secret sharing with small share size

With the new construction of DTPKE developed above, we are now ready to
construct our efficient multi-secret sharing scheme. Assume there are n users
and ` secrets. As briefly explained in section 4.2, we divide the secrets into log n
parts according to their threshold ranges, i.e., [1, 2),[2, 4), . . . , [n/2, n). For the

18
secrets in the range of [δ/2, δ), we will run an independent instance of our general
construction of multi-secret sharing, instantiating the underlying DTPKE with
the new scheme we introduce in section 4.2.
Note that the generic construction will be slightly altered: for each threshold
range [δ/2, δ), the combining key CK is dispersed using an IDS with threshold
δ/2. Since our new DTPKE for threshold range [δ/2, δ) has the combining key
with the size O(δ/2) (growing linearly with the size of the range instead of
the largest threshold value n), running an IDS on this CK will yield share size
O(δ/2)/(δ/2) = O(1). Thus, we will have final share size |C|(1/t1 + 1/t2 + . . . +
1/t` )+O(log n) where |C| is the ciphertext size of each message and t1 , . . . , t` are
the threshold values for the corresponding secrets. The first term is essentially
the smallest size corresponding to the amount of information in the secrets, and
the second part is the overhead we are aiming to minimize in this paper.
Given an efficient IDS (IDA.Disperse, IDA.Rec), and our new DTPKE
(PD.Setup, PD.KeyGen, PD.Enc, PD.ShareDecrypt, PD.Combine),
the details of our final construction of multi-secret sharing are presented as
follows:

– Share: The algorithm takes the security parameter λ, the set P of n users,
and the secrets s1 , . . . , s` to be distributed as inputs. It first divides these
secrets into log n parts ∆1 , . . . , ∆log n , according to the threshold values,
where ∆u := [2u−1 , 2u ) for u = 1, . . . , log n. Here si with threshold ti belongs
to ∆u if ti ∈ ∆u . For each group ∆u , the algorithm runs PD.Setup(λ) to
generate parameters {(M Ku , EKu , CKu )}u=1,...,log n .
The algorithm then encrypts all the secrets using the corresponding master
public keys and the threshold values to generate the ciphertext {c1 , . . . , c` },
where ci = PD.Enc(EKu , ti , si ) if si is in group ∆u .
Now the algorithm runs the IDS on each ciphertext ci using thresholds ti ,
i.e., the shares of ci are generated as {ci,j }j=1,...,n ← IDA.Disperse(ci , ti ).
It also runs the IDS on each combining key CKu using threshold 2u−1 and
gets the shares {CKu,j }j=1,...,n .
For each user j, the algorithm runs PD.KeyGen on each range of thresh-
olds to generate key pairs (upkj,u , uskj,u ) ← PD.KeyGen(M Ku , j) for
j = 1, . . . , n. Also, it distributes the corresponding shares of ciphertexts
and combining keys to this user.
This algorithm ends with each user j receiving his shares of ciphertexts
{ci,j }i=1,...,` , his shares of combining keys {CKu,j }u=1,...,log n , and his key
pairs {(upkj,u , uskj,u )}u=1,...,log n .

– Reconstruct: A set S of tk users jointly run this protocol. Each user j ∈

S takes the index k and his share {(uskj,u , upkj,u ), CKu,j , ci,j }u∈[log n] as
inputs. The users first jointly run the IDA.Rec protocol to reconstruct
the ciphertext ck and the combining key CKu (assuming tk ∈ [2u−1 , 2u ))
that were dispersed using thresholds tk , 2u−1 respectively, i.e., they jointly
reconstruct
ck ← IDA.Rec({ck,j }j∈S ); and CKu ← IDA.Rec({CKu,j }j∈S ) .

19
 Next, each user j in the set S partially decrypts the ciphertext, i.e.,

σk,j ← PD.ShareDecrypt(uskj,u , ck )

to get decryption share σk,j .

Finally, they jointly compute the corresponding secret

sk ← PD.Combine({σk,j }j∈S , CKu , ck ) ,

and each party outputs the secret sk .

Efficiency: For each secret si with threshold ti such that ti ∈ [δ/2, δ) where
δ = 2u−1 for some u ∈ [log n], the corresponding ciphertext ci will be dispersed
using threshold ti which will have size |C|/ti (using, e.g., Rabin IDS [23], where
|C| is the ciphertext size). Thus, all the ciphertext shares have size |C|/t1 +
|C|/t2 + · · · + |C|/t` in total assuming all the ciphertexts are the same length.
Regarding the combining key shares, there are log n combining keys, each with
size |CKu | = O(2u ). They will be dispersed using threshold 2u−1 so that each
contributes O(1) to the share size. Hence, the total size from combining keys
is O(log n). Additionally, there are log n user secret keys with constant size (or
simply security parameter λ) each; thus the size from this part is O(log n). Since
we consider the case where both n, ` are poly(λ), each share size is bounded by
1 1
|C| + ··· + + O(log `).
t1 t`

Note that our ciphertexts have 2 more group elements than the plaintext, as
we consider the case that ` is large, this little overhead is subsumed by the
dominating terms. Here we ignore the λ factor at the overhead term.
As noted in the Introduction, we here also briefly compare the efficiency of
our construction with other schemes in the literature that utilize a public bulletin
board. Remark that our scheme achieves O(log `) share size for each user. If we
encrypt the shares of users with a secret key and put the encryptions in a public
bulletin board similar to [12, 18], then we achieve O(log `) size public storage
together with constant size share for each user, which is the secret key. Thus,
the total size of the bulletin board will be O(log ` · n). However, [12, 18] achieve
only O(` · n) size bulletin board.

Correctness: This is very similar to the correctness of the generic construction,

with the only difference being that the combining keys are dispersed; however, as
long as there are enough shares, the combining key can be reconstructed trivially
from the IDS property.

Security: The only difference with the generic construction is that the combining
keys are also dispersed here. Note that, they are given out directly in the generic
construction, thus the security is not influenced. Combining Theorem 1 and
Theorem 2, we conclude the section with the following theorem:

20
Theorem 3. Suppose λ is the security parameter, under the MSE-DH assump-
tion, there exists a computational secure (t1 , . . . , t` )-multi-secret sharing scheme
distributing ` secrets with length m each, having share size at
 
1 1
O m · ( + · · · + ) + log ` .
t1 t`

5 A fair MPC protocol with smaller private state

A multi-party computation (MPC) protocol [9, 28] allows a set of parties to

securely compute a function f in a distributed way while ensuring the privacy of
the users’ input and the correctness of the output, in the presence of dishonest
users. Besides these basic correctness and privacy requirements, a secure multi-
party computation protocol is highly desirable to achieve robustness (the honest
parties learn their output even some parties play maliciously), fairness (if the
honest parties do not learn their output, then the corrupted parties also cannot
learn their output). MPC protocols can be divided into two groups : ones that
require an honest majority and ones that can achieve security even when there
is no honest majority. Goldreich et al. [9] constructed two different secure MPC
protocols : one achieves security in the passive model even when there is only one
honest user, and one achieves security in the active model under the condition
of honest majority. After this seminal work, most of the works on MPC focus
on these two settings individually.
In [14], Ishai et al. aimed to achieve the best of both, and combined the two
protocols into one that enjoys full security in the presence of any number of pas-
sive corruptions and a minority of active corruptions. Briefly, given the function
f and the inputs of n parties x1 , ..., xn , the parties follow a non-robust MPC
protocol to compute their shares yi . If this phase terminates successfully, then
the parties collude their shares yi to output y = f (x1 , ..., xn ). If the adversary
aborts the computation in this phase, then the parties follow a robust MPC
protocol to complete the computation of y = f (x1 , ..., xn ). Even though combin-
ing two types of protocols into single one incorporates the relative advantages
of both types, it possesses some drawbacks. If the first phase terminates with
abort, the output might already been revealed to the adversary, thus, proceeding
the protocol would violate the security.
Hirt et al. [13] circumvented the above restriction and provide a dynamic
tradeoff between active and passive corruption. They proposed a protocol that
enjoys security in the presence of t < n passive adversaries, and full security in
presence of t < n/2 active adversaries. Moreover, the protocol also guarantees
full security in the presence of mix corruptions, as long as at most k of them
are actively corrupted and less than n − k parties are corrupted in total. To this
aim, they introduce a new primitive “gradual verifiable secret sharing (VSS)”,
which enables the protocol to release the secret gradually in the reconstruction
phase. By this way, the protocol still guarantees enough secrecy for the honest
parties even if it aborts during the reconstruction.

21
 To be more specific, a gradual VSS is a secret sharing scheme in which instead
of the secret s, the random secrets s1 , . . . , sn−1 where s1 + . . . + sn−1 = s, are
shared among users in a way that each si is shared with threshold i. 12 In
reconstruction protocol, the shares are released one by one in decreasing order
of thresholds. Particularly, in stage i of the reconstruction protocol, if at least
(i + 1) users provide correct shares, then the protocol outputs the corresponding
secret si . Otherwise, the protocol is aborted, and each user outputs a set of
corrupted users that did not provide correct shares. If there is no abort, each
user will eventually get the secret s = s1 + . . . + sn−1 . Remark that an abort
at stage i prevents the adversary from learning si , . . . , s1 and thus the secret s.
From this fact, the gradual VSS enables the protocol to preserve as much secrecy
as possible.
The gradual VSS can be seen as a (1, 2, . . . , n − 1)-MSSS that reconstructs
the secrets one by one in a decreasing order of the thresholds. In the distribution
of each secret, Hirt et al. [13] utilize (n − 1) independent Shamir secret sharing
schemes to implement gradual VSS. Thus, the first phase of the protocol results
in linear size shares for users in the terms of the number users. However, if the
protocol employs our construction given in section 4 as gradual secret sharing,
then the size of the shares will be only logarithmic in the number of users.
The only task left after replacing the “trivial” secret sharing scheme with our
efficient MSSS is that we have to make it verifiable. In other words, the users
should be convinced that the shares output by the protocol are valid. Besides,
they have to prove the validity of their shares when they pool them to get the
secrets si . Fortunately, it is not hard to turn our construction to a verifiable one.
In brief, in the Share protocol, each user receives a secret key, ciphertext shares
and combining key shares generated by the IDS. For the verifiability, the dealer
has to prove that the secret key is in the form g Pi (γ) which can be done easily by
checking some bilinear relation. The validity of the shares can be inherited from
a verifiable IDS [5] (or directly applying zk-SNARK [2, 10, 19, 20]). While in the
Reconstruct protocol, each user proves in zero-knowledge that the decryption
share is in the form of σ = e(g, h)kα·A(γ)·Pi (γ) which could be done efficiently
(e.g., σ-protocol type of ZK proof [24]). At last, each user proves the validity of
the shares of the ciphertexts and the combining keys (which can always be done
via zk-SNARK for practical instantiation) 13 . Note that for verifiability, some
extra communication is necessary, however, they do not belong to the private
states that each user has to store. For the details of each underlying tools, we
refer to the references [5, 7, 24].

12
The shares are the outputs of a general MPC protocol by running [9] in the first
phase. Note that even though the GMW protocol does not provide strong enough
robustness or fairness, however, malicious parties do not gain any advantage aborting
in this phase as they only see shares.
13
Here, it will be helpful to distinguish between a one-time public parameter-generation
and a full-time public bulletin board: the former is the one-time setup; more impor-
tantly, it can be performed by the data owners for our setting. However, the latter
requires the maintenance of the bulletin board during the life-time of the shares

22
6 Conclusions and Open Problems
In this paper, we constructed a share size (near) optimal multi-secret sharing
scheme in the computational setting. Our construction achieves a share/overhead
size grows logarithmically in the number of secrets, which significantly improves
the previously known results about multi-secret sharing that the share size grows
linear in the number of secrets. We use a tool of dynamic threshold public key
encryption scheme as the underlying building block. In order to achieve our
goal of share size efficiency, we constructed a new DTPKE that has a constant
size ciphertext and shorter combining key, which might be of independent in-
terests. We also demonstrate two interesting applications of our MSSS scheme
to decentralized storage network and to the setting of fair secure multiparty
computation.
There are also some open problems remain. Since a MSSS has a unique fea-
ture that multiple independent secrets can be shared without the need of sharing
them one by one, an interesting question could be finding other applications to
distributive cryptography that inherits our share size efficiency. Furthermore, our
main building block of a new, efficient DTPKE (and the underlying technique)
might also be applicable to e.g., constructions of attribute based encryption.
Also, showing some lower bound on the parameter efficiency on the DTPKE is
intriguing, intuitively, it seems hard to get a DTPKE scheme with all parameters
sublinear, since there is not enough space to encode the corresponding informa-
tion according to all the possible thresholds, but formally showing such a result
will be quite interesting.

References
1. A. Beimel, A. Ben-Efraim, C. Padró, and I. Tyomkin. Multi-linear secret-sharing
schemes. In Theory of Cryptography-TCC 2014, pages 394–418, 2014.
2. N. Bitansky, A. Chiesa, Y. Ishai, R. Ostrovsky, and O. Paneth. Succinct non-
interactive arguments via linear interactive proofs. In Theory of Cryptography -
10th Theory of Cryptography Conference, TCC 2013, Tokyo, Japan, March 3-6,
2013. Proceedings, pages 315–333, 2013.
3. G. R. Blakley. Safeguarding cryptographic keys. Managing Requirements Knowl-
edge, International Workshop on, page 313, 1979.
4. C. Blundo, A. D. Santis, G. D. Crescenzo, A. G. Gaggia, and U. Vaccaro. Multi-
secret sharing schemes. In CRYPTO ’94, 1994, pages 150–163, 1994.
5. C. Cachin and S. Tessaro. Asynchronous verifiable information dispersal. In DISC
2005, pages 503–504, 2005.
6. C. Delerablée and D. Pointcheval. Dynamic threshold public-key encryption. In
Advances in Cryptology - CRYPTO 2008, pages 317–334, 2008.
7. A. Fiat and A. Shamir. How to prove yourself: Practical solutions to identification
and signature problems. In CRYPTO, pages 186–194, 1986.
8. S. D. Galbraith, K. Harrison, and D. Soldera. Implementing the tate pairing. In
Algorithmic Number Theory 2002, pages 324–337, 2002.
9. O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game or
a completeness theorem for protocols with honest majority. In STOC 87, pages
218–229.

23
10. J. Groth. Short pairing-based non-interactive zero-knowledge arguments. In Ad-
vances in Cryptology - ASIACRYPT 2010 - 16th International Conference on the
Theory and Application of Cryptology and Information Security, Singapore, De-
cember 5-9, 2010. Proceedings, pages 321–340, 2010.
11. J. Herranz, A. Ruiz, and G. Sáez. Sharing many secrets with computational prov-
able security. Inf. Process. Lett., 113(14-16):572–579, 2013.
12. J. Herranz, A. Ruiz, and G. Sáez. New results and applications for multi-secret
sharing schemes. Des. Codes Cryptography, 73(3):841–864, 2014.
13. M. Hirt, C. Lucas, and U. Maurer. A dynamic tradeoff between active and passive
corruptions in secure multi-party computation. In CRYPTO 2013,, pages 203–219,
2013.
14. Y. Ishai, E. Kushilevitz, Y. Lindell, and E. Petrank. On combining privacy with
guaranteed output delivery in secure multiparty computation. In Advances in
Cryptology - CRYPTO 2006, volume 4117, pages 483–500, 2006.
15. W.-A. Jackson, K. M. Martin, and C. M. O’Keefe. Multisecret threshold schemes.
In CRYPTO 1993, pages 126–135, 1993.
16. E. D. Karnin, S. Member, J. W. Greene, S. Member, and M. E. Hellman. On secret
sharing systems. IEEE Transactions on Information Theory, 29:35–41, 1983.
17. H. Krawczyk. Secret sharing made short. In CRYPTO ’93, pages 136–146, 1993.
18. H. Lin and Y. Yeh. Dynamic multi-secret sharing scheme. Int. J. Contemp. Math.
Sciences, pages 37–42, 2008.
19. H. Lipmaa. Progression-free sets and sublinear pairing-based non-interactive zero-
knowledge arguments. In Theory of Cryptography - 9th Theory of Cryptography
Conference, TCC 2012, Taormina, Sicily, Italy, March 19-21, 2012. Proceedings,
pages 169–189, 2012.
20. H. Lipmaa. Succinct non-interactive zero knowledge arguments from span pro-
grams and linear error-correcting codes. In Advances in Cryptology - ASIACRYPT
2013 - 19th International Conference on the Theory and Application of Cryptol-
ogy and Information Security, Bengaluru, India, December 1-5, 2013, Proceedings,
Part I, pages 41–60, 2013.
21. T. N. M. Itoh, A. Saito. Secret sharing scheme realizing general access structure.
IEEE Globecom, page 99102, 1987.
22. B. Masucci. Sharing multiple secrets: Models, schemes and analysis. Des. Codes
Cryptography, 39(1):89–111, 2006.
23. M. Rabin. Efficient dispersal of information for security, load balancing, and fault
tolerance. Journal of the ACM, 36:335–348, 1989.
24. C.-P. Schnorr. Efficient identification and signatures for smart cards. In CRYPTO,
pages 239–252, 1989.
25. A. Shamir. How to share a secret. Communications of the ACM, 22(22):612–613,
1979.
26. C. Tartary, J. Pieprzyk, and H. Wang. Verifiable multi-secret sharing schemes
for multiple threshold access structures. In Information Security and Cryptology,
Third SKLOIS Conference, Inscrypt 2007, Xining, China, August 31 - September
5, 2007, Revised Selected Papers, pages 167–181, 2007.
27. M. van Dijk, W.-A. Jackson, and K. M. Martin. A general decomposition construc-
tion for incomplete secret sharing schemes. Des. Codes Cryptography, (3):301–321,
1998.
28. A. C. Yao. Protocols for secure computations (extended abstract). In FOCS 82,
pages 160–164, 1982.

24