Construction of Threshold Public-Key
Encryptions
through Tag-Based Encryptions
Seiko Arita and Koji Tsurudome
Institute of Information Security,
Yokohama, Kanagawa, Japan{arita,mgs068101}@iisec.ac.jp

Abstract. In this paper, we propose a notion of threshold tag-based
encryption schemes that simpliﬁes the notion of threshold identity-based
encryption schemes, and we show a conversion from any stag-CCAsecure threshold tag-based encryption schemes to CCA-secure threshold public-key encryption schemes. Moreover, we give two concrete constructions of stag-CCA-secure threshold tag-based encryption schemes,
under the decisional bilinear Diﬃe-Hellman assumption and the decisional linear assumption, respectively. Thus, we obtain two concrete constructions of threshold public-key encryption schemes, both of which are
non-interactive, robust and can be proved secure without random oracle
model. Our threshold public-key encryption schemes are conceptuallymore simple and shown to be more eﬃcient than those of Boneh, Boyenand Halevi.
Keywords: threshold public-key encryption schemes, tag-based encryption schemes, the decisional bilinear Diﬃe-Hellman assumption, thedecisional linear assumption.

1

Introduction

A threshold public-key encryption scheme is a public-key encryption scheme
where a private key is distributed and shared among several decryption servers
and some number of those decryption servers must cooperate to decrypt any ciphertext [2,4,9]. In a model of k-out-of-n threshold public-key encryption scheme,
an entity, called combiner, has a ciphertext C that it wishes to decrypt. The combiner sends C to the decryption servers, and receives partial decryption sharesfrom at least k out of the n decryption servers. It then combines these k partial
decryptions into a complete decryption of C. Ideally, it is desirable that there isno other interaction in the system, namely the servers need not talk to each otherduring decryption. Such threshold systems are called non-interactive. Often one
requires that threshold decryption be robust, namely if threshold decryption ofa valid ciphertext fails, the combiner can identify the decryption servers that
supplied invalid partial decryptions.
M. Abdalla et al. (Eds.): ACNS 2009, LNCS 5536, pp. 186–200, 2009.
c Springer-Verlag Berlin Heidelberg 2009Construction of Threshold Public-Key Encryptions

187

In 2006, Boneh, Boyen and Halevi [2] gave a construction of CCA-securethreshold public-key encryption scheme by converting a sID-CPA-secure threshold identity-based encryption scheme into it, which in turn is constructed basedon the decisional bilinear Diﬃe-Hellman assumption. Their CCA-secure threshold public-key encryption scheme is the ﬁrst one that is non-interactive, robust
and can be proved secure without random oracle model.
On the other hand, in 2006, Kiltz [6] proposed a notion of tag-based encryption scheme through simplifying the notion of identity-based encryption schemes[3,7], and gave a transformation from any stag-CCA-secure tag-based encryption
schemes to CCA-secure public-key encryption schemes.
In this paper, we propose a notion of threshold tag-based encryption schemesthat simpliﬁes the notion of threshold identity-based encryption schemes in asimilar way as [6], and then we show a conversion from any stag-CCA-securethreshold tag-based encryption schemes to CCA-secure threshold public-key encryption schemes, that is an adaption of the CHK transform [5] to the setting ofthreshold encryption. Moreover, we give two concrete constructions of stag-CCAsecure threshold tag-based encryption schemes, that are non-interactive, robust
and can be proved without random oracle model, under the decisional bilinear
Diﬃe-Hellman assumption and the decisional linear assumption, respectively.
Thus, we obtain two concrete constructions of threshold public-key encryption
schemes, through applying the conversion to the two threshold tag-based encryption schemes, both of which are non-interactive, robust and can be proved
secure without random oracle model.
In the threshold identity-based encryption scheme of [2], a decryption shareis regarded as a ciphertext of private key share corresponding to decrypter’s ID.
But in our threshold tag-based encryption scheme, a decryption share can be
regarded naturally as a partial decrypted ciphertext. As a result, our thresholdpublic-key encryption schemes, obtained through the conversion, are conceptually more simple and shown to be more eﬃcient than those of [2].

2Threshold Tag-Based Encryptions and Their
Conversion to Threshold Public-Key Encryptions

In this section, after reviewing the deﬁnition of threshold public-key encryptions
and their security following [2], we propose a notion of threshold tag-based encryptions and show a conversion from any stag-CCA-secure threshold tag-based
encryption schemes to CCA-secure threshold public-key encryption schemes.
2.1

Threshold Public-Key Encryption

Scheme. A threshold public-key encryption scheme TPKE consists of ﬁve algorithms:
TPKE = (Setup, Encrypt, ShareDec, ShareVf, Combine).
Setup takes as input the number of decryption servers n, a threshold k (1 ≤ k ≤n), and a security parameter Λ. It outputs a triple (P K, V K, SK) where P K

188

S. Arita and K. Tsurudome

is a public key, V K is a veriﬁcation key and SK = (SK1 , · · · , SKn ) is a vectorof n private key shares. Encrypt takes as input a public key P K and a message
M , and it outputs a ciphertext C. ShareDec takes as input a public key P K, aciphertext C, and the i-th private key share (i, SKi ). It outputs a decryption
share μi of the encrypted message, or a special symbol (i, ⊥). ShareVf takes as
input a public key P K, veriﬁcation key V K, ciphertext C and a decryption
share μi . It outputs valid or invalid. When the output is valid, we say that μi is
a valid decryption share of C. Combine takes as input P K, V K, ciphertext C,
and k decryption shares {μ1 , · · · , μk }. It outputs a message M or ⊥.
For any output (P K, V K, SK) of Setup(n, k, Λ), we require the two consistency properties:
1. For any valid ciphertext C, if μi ← ShareDec(P K, i, SKi , C), thenShareVf(P K, V K, C, μi ) is valid.
2. If C is the output of Encrypt(P K, M ) and S = {μ1 , · · · , μk } is a set ofdecryption shares μi ← ShareDec(P K, i, SKi , C) for k distinct private key
shares in SK, then Combine(P K, V K, C, S) = M .
Security. Security of threshold public-key encryption scheme TPKE is deﬁned interms of chosen ciphertext security and decryption consistency. Chosen ciphertext security is deﬁned using the following game between a challenger and an
adversary. Both are given n, k, Λ as input.
1. Init. The adversary outputs a set S ⊂ {1, · · · , n} of k − 1 decryption servers
to corrupt.
2. Setup. The challenger runs Setup(n, k, Λ) to obtain a random instance(P K, V K, SK). It gives the adversary P K, V K, and all (j, SKj ) for j ∈ S.
3. Query phase 1. The adversary adaptively issues decryption queries (C, i)
where C ∈ {0, 1}∗ and i ∈ {1, · · · , n}. The challenger responds with
ShareDec(P K, i, SKi , C).
4. Challenge. The adversary outputs two messages M0 , M1 of equal length.
The challenger picks a random b ∈ {0, 1} and lets C ∗ ← Encrypt(P K, Mb ).
It gives C ∗ to the adversary.
5. Query phase 2. The adversary issues further decryption queries (C, i), under
the constraint that C = C ∗ . The challenger responds as in Query Phase 1.
6. Guess. The adversary outputs its guess b ∈ {0, 1} for b and wins the gameif b = b .
We deﬁne an advantage of adversary A for threshold public-key encryption
scheme TPKE with respect to chosen ciphertext security as Advcca
A,TPKE,n,k (Λ) =|Pr[b = b ] − 1/2|.
Decryption consistency is deﬁned using the following game. The game starts
with the Init, Setup, and Query phase 1 steps as in the game above. The adversary then outputs a ciphertext C and two sets of decryption shares S ={μ1 , · · · , μk } and S  = {μ1 , · · · , μk } each of size k. The adversary wins if:

Construction of Threshold Public-Key Encryptions

189– The shares in S and S  are valid decryption shares for C under V K.
– S and S  each contain decryption shares from k distinct servers.
– Combine(P K, V K, C, S) = Combine(P K, V K, C, S  ), with either side notequal to ⊥.
We let Advdc
A,TPKE,n,k (Λ) denote the probability that the adversary A wins thisgame.
Definition 1. We say that a threshold public-key encryption scheme TPKE is
CCA-secure if for any n, k (1 ≤ k ≤ n) and any probabilistic polynomial timedc
algorithm A, both of the functions Advcca
A,TPKE,n,k (Λ) and AdvA,TPKE,n,k (Λ) are
negligible.
2.2

Threshold Tag-Based Encryption

A notion of threshold tag-based encryptions is obtained by simplifying threshold
identity-based encryption schemes in a similar way as [6] in the non-thresholdsetting. Threshold tag-based encryptions simply needs a tag as input in addition
to ordinary inputs of threshold encryptions.
Scheme. A threshold tag-based encryption scheme TTBE consists of ﬁve algorithms:
TTBE = (Setup, Encrypt, ShareDec, ShareVf, Combine).
Setup takes as input the number of decryption servers n, a threshold k (1 ≤k ≤ n) and a security parameter Λ. It outputs a triple (P K, V K, SK) whereP K is a public key, V K is a veriﬁcation key, and SK = (SK1 , · · · , SKn ) is avector of n private key shares. Encrypt takes as input a public key P K, a tagt and a message M , and it outputs a ciphertext C. ShareDec takes as input apublic key P K, a ciphertext C, a tag t, and a i-th private key share (i, SKi ).
It outputs a decryption share μi of the encrypted message, or a special symbol(i, ⊥). ShareVf takes as input P K, V K, a ciphertext C, a tag t and a decryption
share μi . It outputs valid or invalid. When the output is valid, we say that μi is
a valid decryption share of C. Combine takes as input P K, V K, a ciphertext C,a tag t and k decryption shares {μ1 , · · · , μk }. It outputs a message M or ⊥.
As in the threshold public-key encryption scheme, we require the following
two consistency properties. Let (P K, V K, SK) be the output of Setup(n, k, Λ).
1. For any tuple (C, t) of a valid ciphertext and a tag, if μi ← ShareDec(P K, i, SKi , C, t), then ShareVf(P K, V K, C, t, μi ) = valid.
2. If C is the output of Encrypt(P K, t, M ) and S = {μ1 , · · · , μk } is a set ofdecryption shares μi ← ShareDec(P K, i, SKi , C, t) for k distinct private key
shares in SK, then Combine(P K, V K, C, t, S) = M .
Security. Security of threshold tag-based encryption scheme TTBE is deﬁned interms of stag-chosen-ciphertext security and stag decryption consistency. Stagchosen ciphertext security is deﬁned using the following game between a challenger and an adversary. Both are given n, k, Λ as input.

190

S. Arita and K. Tsurudome

1. Init. The adversary outputs a target tag t∗ that it wants to attack and a setof k − 1 decryption servers S ⊂ {1, · · · , n} that it wants to corrupt.
2. Setup. The challenger runs Setup(n, k, Λ) to obtain a random instance(P K, V K, SK). It gives the adversary P K, V K, and all (j, SKj ) for j ∈ S.
3. Query phase 1. The adversary adaptively issues decryption share queries((C, t), i) with i ∈ {1, · · · , n}, under the constraint that t = t∗ . The challenger responds with ShareDec(P K, i, SKi , C, t).
4. Challenge. The adversary outputs two messages M0 , M1 of equal length. The
challenger picks a random b ∈ {0, 1} and lets C ∗ ← Encrypt(P K, t∗ , Mb ). It
gives C ∗ to the adversary.
5. Query phase 2. The adversary adaptively issues decryption share queries((C, t), i) with i ∈ {1, · · · , n}, under the constraint that t=t∗ . The challenger
responds as in phase 1.
6. Guess. The adversary outputs its guess b ∈ {0, 1} for b and wins the gameif b = b .
We deﬁne an advantage of adversary A for threshold tag-based encryption
scheme TTBE with respect to stag-chosen-ciphertext security as Advstag−cca
A,TTBE,n,k (Λ)= |Pr[b = b ] − 1/2|.
Stag decryption consistency is deﬁned using the following game. The gamestarts with the Init, Setup and Query phase 1 steps as in the game above. The
adversary then outputs a tag t, a ciphertext C and two sets of decryption shares
S = {μ1 , · · · , μk } and S  = {μ1 , · · · , μk } each of size k. The adversary wins if:
1. The shares in S and S  are valid decryption shares for (C, t) under V K.
2. S and S  each contain decryption shares from k distinct servers.
3. Combine(P K, V K, C, t, S) = Combine(P K, V K, C, t, S  ), with either side notequal to ⊥.
We let Advstag−dc
A,TTBE,n,k (Λ) denote the probability that the adversary A wins
this game.
Definition 2. We say that a threshold tag-based encryption scheme TTBE isstag-CCA-secure if for any n, k (1 ≤ k ≤ n) and any probabilistic polynomialstag−dc
time algorithm A, both of the functions Advstag−cca
A,TTBE,n,k (Λ) and AdvA,TTBE,n,k (Λ)
are negligible.
2.3

Conversion from Threshold Tag-Based Encryption Schemes
into Threshold Public-Key Encryption Schemes

In this section we show a conversion from any stag-CCA-secure threshold tagbased encryption scheme to CCA-secure threshold public-key encryption scheme.
The conversion is a direct adjustment of the conversions of [5,6] into the thresholdsetting.
We convert a given threshold tag-based encryption scheme
TTBE = (Setupttbe , Encryptttbe , ShareDecttbe , ShareVfttbe , Combinettbe )into a threshold public-key encryption scheme

Construction of Threshold Public-Key Encryptions

191

TPKE = TT2TP(TTBE, S) = (Setuptpke , Encrypttpke , ShareDectpke , ShareVftpke , Combinetpke )using a strong one-time signature S = (KG, SGN, VF) as in Figure 1.
Setuptpke (n, k, Λ) :(P K, V K, SK) ← Setupttbe (n, k, Λ), output (P K, V K, SK).
Encrypttpke (P K, M ) :(sigk, verk) ← KG(Λ), Cttbe ← Encryptttbe (P K, verk, M ), σ ← SGN(sigk, Cttbe );output Ctpke = (Cttbe , verk, σ).
ShareDectpke (P K, i, SKi , Ctpke = (Cttbe , verk, σ)) :If VF(verk, Cttbe , σ) = invalid then output μi = (i, ⊥),else output ShareDecttbe (P K, i, SKi , Cttbe , verk).
ShareVftpke (P K, V K, Ctpke = (Cttbe , verk, σ), μi ) :If VF(verk, Cttbe , σ) = invalid then output invalid,
else output ShareVfttbe (P K, V K, Cttbe , verk, μi ).
Combinetpke (P K, V K, Ctpke = (Cttbe , verk, σ), {μ1 , · · · , μk }) :If ∃i, μi = (i, ⊥) or ShareVftpke (P K, V K, Ctpke , μi ) = invalid then output ⊥,else output Combinettbe (P K, V K, Cttbe , verk, {μ1 , · · · , μk }).
Fig. 1. TT2TP: Conversion from threshold tag-based encryption schemes to thresholdpublic-key encryption schemes

Theorem 1. If a threshold tag-based encryption scheme TTBE is stag-CCAsecure and S is a strong one-time signature, then the threshold public-key encryption scheme TPKE = TT2TP(TTBE, S) is CCA-secure.
More precisely, for an arbitrary eﬃcient adversary A against chosen ciphertext security of TPKE, there exists an eﬃcient algorithm B against stag-chosenciphertext security of the underlying TTBE and a forger F of the underlying S
that satisfy
stag−ccaot−cma(Λ).
AdvccaA,TPKE,n,k (Λ) ≤ AdvB,TTBE,n,k (Λ) + AdvF ,S(Here, Advot−cma
denotes the advantage of forger F against one-time signature
F ,S
S in the usual game of strong chosen-message attack with at most one signing
query.) Similarly, for an arbitrary eﬃcient adversary A against decryption consistency of TPKE, there exists an eﬃcient algorithm B  against stag decryption
consistency of the underlying TTBE and a forger F  of the underlying S thatsatisfystag−dcot−cma(Λ).
Advdc
A ,TPKE,n,k (Λ) ≤ AdvB ,TTBE,n,k (Λ) + AdvF  ,S
Proof. First, we consider chosen ciphertext security of TPKE. Let A be an arbitrary eﬃcient adversary against chosen ciphertext security of TPKE. Using
adversary A, we build an algorithm B that attacks stag-chosen-ciphertext security of the underlying TTBE.

192

S. Arita and K. Tsurudome

Algorithm B proceeds as follows:
1. Initialization. Given input (n, k, Λ) algorithm B runs A on the same input toobtain a list S (⊂ {1, · · · , n}) of the k − 1 servers that A wishes to corrupt.
Next, B runs KG on Λ to obtain a signing key sigk ∗ and a veriﬁcation key
verk ∗ . It outputs the set S and the target tag t∗ = verk ∗ to the TTBE
challenger.
2. Setup. The TTBE challenger runs Setupttbe (n, k, Λ) to obtain (P K, V K, SK).
It gives B the values P K, V K, and all (j, SKj ) for j ∈ S. Algorithm B forwards
these values to A.
3. Query Phase 1. Adversary A adaptively issues decryption queries of the form
(Ctpke , i) where Ctpke = (Cttbe , verk, σ) and i ∈ {1, · · · , n}. For each such aquery (Ctpke , i), B proceeds as follows:(a) If VF(verk, Cttbe , σ) = invalid then B gives μi = (i, ⊥) to A.
$(b) Else if verk = t∗ then B outputs b ← {0, 1} and aborts.
(c) Else B issues a decryption query ((Cttbe , verk), i) to own TTBE decryption oracle and obtains a decryption share μi in return. It gives thedecryption share μi to A.
4. Challenge. Adversary A outputs two equal-length messages M0 and M1 . B
forwards these M0 and M1 to its own TTBE challenger. The TTBE chal∗of Mb under t∗ for some b ∈ {0, 1}.
lenger responds with the encryption Cttbe∗∗
B then runs SGN on (sigk , Cttbe ) to obtain a signature σ ∗ , and it gives
∗
∗
Ctpke
= (Cttbe, t∗ , σ ∗ ) to A as challenge ciphertext.
∗), i).
5. Query Phase 2. A continues to issue decryption queries (Ctpke (= Ctpke
B responds as in Query Phase 1.
6. Guess. Eventually, A outputs its guess b ∈ {0, 1} for b. B forwards b to the
TTBE challenger and wins the game if b = b .
This completes the description of algorithm B.
Let Abort be the event that B aborts in Query Phase 1 or 2 during the simulation. As easily seen, as long as Abort does not happen, B’s simulation of TPKE
cca
challenger is perfect. Therefore, we have |Advstag−cca
B,TTBE,n,k (Λ)−AdvA,TPKE,n,k (Λ)| <Pr[Abort]. By deﬁnition, Abort means A’s forgery of valid signature σ underveriﬁcation key verk ∗ , and it leads to a forger F of S satisfying Pr[Abort] ≤stag−ccaot−cmaAdvot−cma. Thus, Advcca(Λ).
A,TPKE,n,k (Λ) ≤ AdvB,TTBE,n,k (Λ) + AdvF ,SF ,SSecond, we see decryption consistency of TPKE. Let A be an arbitrary eﬃcient adversary against decryption consistency of TPKE. Using adversary A , webuild an algorithm B  that attacks stag decryption consistency of the underlying
TTBE.
Algorithm B  proceeds exactly as algorithm B, until A outputs the challengeˆ σ̂), S, S  ), and then B  outputs (verk,
ˆ Cttbeˆ = (Cttbe
ˆ , verk,
ˆ , S, S  ) after(Ctpkeˆverifying validity of σ̂ under verk.
Just as in the case of chosen ciphertext security, let Abort be the event that B aborts in Query Phase 1 during the simulation. Then, as above, |Advstag−dc
B ,TPKE,n,k (Λ)
(Λ)|<
Pr[Abort].
Again,
Abort
leads
to
a
forgerF
of S, and we− Advdc
A ,TTBE,n,k
stag−dcdcot−cmahave AdvA ,TPKE,n,k (Λ) ≤ AdvB ,TTBE,n,k (Λ) + AdvF  ,S (Λ).
2Construction of Threshold Public-Key Encryptions

3

193

Construction of Threshold Tag-Based Encryption
SchemesIn this section, we construct two concrete stag-CCA-secure threshold tag-based
encryption schemes based on the decisional bilinear Diﬃe-Hellman assumption
and on the decisional linear assumption, respectively.
3.1

Preliminaries

We recall necessary primitives around bilinear maps.
Bilinear Maps. Let G be a group of prime order p with generator g. Let G1 beanother group of prime order p. A bilinear map e : G × G → G1 is a map withthe properties:
1. For all u, v ∈ G and a, b ∈ Zp , it holds e(ua , v b ) = e(u, v)ab .
2. e(g, g) = 1.
3. For all u, v, e(u, v) is eﬃciently computable.
Decisional Bilinear Diﬃe-Hellman Assumption. If a bilinear Diﬃe-Hellman tuple(g, g a , g b , g c , e(g, g)abc ) is indistinguishable from a bilinear random tuple(g, g a , g b , g c , e(g, g)d ), we say the decisional bilinear Diﬃe-Hellman assumption
holds. More formally, as for algorithm GDBDH that takes a security parameter Λand outputs order p, generator g, and descriptions of groups G and G1 with bilinear
bdh-1
map e : G × G → G1 , the following two experiments are deﬁned. ExpGon
DBDH ,A
input Λ generates param = (p, g, G, G1 , e) by GDBDH (Λ) and chooses three random elements a, b, c from Zp . Then it invokes A on (param, g, g a , g b , g c , e(g, g)abc )bdh-2
chooses four random elements
and returns its output. On a while, ExpG
DBDH ,Aa, b, c, d from Zp and returns A(param, g, g a , g b , g c , e(g, g)d ).
We say that the decisional bilinear Diﬃe-Hellman (DBDH) assumption holds fordefG
if for any probabilistic polynomial time algorithm A, Advdbdh
A,GDBDH (Λ) = DBDH bdh-1

bdh-2
 Pr[Exp is a negligible function
(Λ)
=
1]
−
Pr[Exp(Λ)=
1]
GDBDH ,AGDBDH ,Aof Λ.
Decisional Linear Assumption. If a linear tuple (g1 , g2 , z, g1r1 , g2r2 , z r1 +r2 ) is indistinguishable from a random tuple (g1 , g2 , z, g1r1 , g2r2 , z s ), we say the decisional
linear assumption holds. More formally, as for algorithm GDLIN that takes
a security parameter Λ and outputs order p, generator g, and descriptions ofgroups G and G1 with bilinear map e : G × G → G1 , the following two exper-1
iments are deﬁned. Explin
GDLIN ,A on input Λ generates param = (p, g, G, G1 , e)
by GDLIN (Λ) and chooses four random elements u, v, r1 , r2 from Zp . Then it
invokes A on (param, g, g u , g v , g r1 , g ur2 , g v(r1 +r2 ) ) and returns its output. On
lin-2
a while, ExpG
chooses ﬁve random elements u, v, r1 , r2 , s from Zp andDLIN ,A
returns A(param, g, g u , g v , g r1 , g ur2 , g vs ).

194

S. Arita and K. Tsurudome

We say that the decisional linear (DLIN) assumption holds for GDLIN if fordef

any probabilistic polynomial time algorithm A, Advdlin=
A,GDLIN (Λ)


-1
lin-2
 Pr[Explin

(Λ)
=
1]
−
Pr[Exp
(Λ)
=
1]
is
a
negligible
function
GDLIN ,AGDLIN ,Aof Λ.
A Construction TTBE1 of Threshold Tag-Based Encryption
Scheme Based on the DBDH Assumption

3.2

Our ﬁrst construction TTBE1 of threshold tag-based encryption scheme is obtained through a simpliﬁcation and “thresholding” of the identity-based encryption scheme of Boneh and Boyen [1].
As easily seen, the identity-based encryption scheme of [1] can be simpliﬁed intoa following tag-based encryption scheme. A public-key is randomly selected elements g1 (= g x ), g2 , h1 on a bilinear group G (with generator g). The corresponding secret key is x. A message M is encrypted with respect to tag t as (C, D, E) =(g r , (g1t h1 )r , M · e(g1 , g2 )r ). Ciphertext (C, D, E) is decrypted with respect to tagt as M = E/e(C, g2 )x if it holds e(C, g1t h1 ) = e(D, g), otherwise M = ⊥.
In the threshold identity-based encryption scheme of [2], which is also based on
the identity-based scheme of [1], a decryption share is regarded as a ciphertext
of private key share corresponding to decrypter’s ID. On a while, in order toconvert the above tag-based encryption scheme into a threshold version, thanks
to the simple setting of tag-based encryption scheme, we can naturally distributethe secret key x into shares {f (i)}i using Shamir’s secret sharing scheme [8] andmake the i-th decryption share to be (C f (i) , E) as the usual threshold version
of ElGamal encryption. More precisely TTBE1 is described in Figure 2.
Setup(n, k, Λ):(p, g, G, G1 , e) ← GDBDH (Λ);$$

x ← Zp , f ← Zp [X] satisfying deg(f ) = k − 1 and f (0) = x;$y, z ← Zp , g1 ← g x , g2 ← g y , h1 ← g z ;P K = (p, G, G1 , e, g, g1 , g2 , h1 ), SK = (f (1), · · · , f (n)), V K = (g f (1) , · · · , g f (n) );return (P K, V K, SK).
Encrypt(P K, t, M ):$r ← Zp , C ← g r , D ← (g1 t h1 )r , E ← M · e(g1 , g2 )r , return Ctbe = (C, D, E).
ShareDec(P K, i, SKi = f (i), Ctbe = (C, D, ·), t):If e(C, g1 t h1 ) = e(D, g) then return μi = (i, ⊥) else return μi = (i, C f (i) ).
ShareVf(P K, V K = (g f (i) ), Ctbe = (C, ·, ·), t, μi = (i, Ci )):If e(Ci , g) = e(C, g f (i) ) then return invalid else return valid.
Combine(P K, V K, Ctbe = (·, ·, E), t, {μ1 = (1, C1 ), · · · , μk = (k, Ck )}):
If ∃i, ShareVf(P K, V Ki , Ctbe , t, μi ) = invalid then return ⊥,else return E/e( ki=1 Ciλi , g2 ) using Lagrange coeﬃcients λ1 , · · · , λksatisfying f (0) = ki=1 λi f (i).
Fig. 2. Threshold Tag-Based Encryption Scheme TTBE1

Construction of Threshold Public-Key Encryptions

195

Theorem 2. Under the DBDH assumption for GDBDH , the threshold tag-based
encryption scheme TTBE1 is stag-CCA-secure.
More precisely, for an arbitrary adversary A against stag-chosen-ciphertext
security of TTBE1 that runs in time at most τ and makes at most Q decryption
queries, there exists an algorithm B for the DBDH problem on GDBDH that runsin time at most τ plus the time to perform O(Q + n) exponentiations and O(Q)pairing computations, and satisﬁes
dbdh
Advstag−cca
A,TTBE1,n,k (Λ) = AdvB,GDBDH (Λ).

For an arbitrary adversary A against stag decryption consistency of TTBE1, it
holds that
Advstag−dc
A ,TTBE1,n,k (Λ) = 0.
Proof. First, we consider stag-chosen-ciphertext security of TTBE1. Let A be an
arbitrary adversary that runs in time at most τ , makes at most Q decryption
queries, and has advantage Advstag−cca
A,TTBE1,n,k (Λ) in attacking TTBE1 in the gameof stag-chosen-ciphertext security. Using the adversary A, we build an algorithm
B that solves the DBDH problem on GDBDH (Λ).
Given (Λ, p, G, G1 , e, g, g a , g b , g c , W ) as input, algorithm B proceeds as follows.
(The aim of B is to distinguish two cases between W = e(g, g)abc or random.)
1. Initialization. Algorithm B invokes adversary A on input (n, k, Λ). Adversary
A outputs a target tag t∗ and a list S = {s1 , · · · , sk−1 }(⊂ {1, · · · , n}) of thek − 1 servers that it wishes to corrupt.
2. Setup. Then, B does the following:∗(a) B sets g1 = g a , g2 = g b and computes h1 = g1−t g γ with a random γ$(← Zp ). (This deﬁnes implicitly as x = a, y = b, z = −t∗ x + γ.) B sets
P K = (p, G, G1 , e, g, g1 , g2 , h1 ).
$(b) Next, B picks k − 1 random integers α1 , · · · , αk−1 ← Zp . (We let f ∈Zp [X] be a polynomial of degree k−1 deﬁned by f (0) = x and f (si ) = αi
for i = 1, · · · , k − 1. B does not know f .) B sets SK|S = (α1 , · · · , αk−1 ).
(c) For i ∈ S, B lets ui = g αi . For i ∈/ S, it computes ui = g1λ0 (g α1 )λ1 · · ·αk−1 λk−1), where λ0 , · · · , λk−1 (∈ Zp ) are the Lagrange coeﬃcients sat(gf (i)isfying f (i) = λ0 f (0) + k−1.) B
j=1 λj f (sj ). (Note ui satisﬁes ui = g
sets V K = (u1 , · · · , un ).
(d) B gives P K, V K and SK|S to A.
3. Phase 1. A issues decryption share queries ((Ctbe , t), i) under the constraint?

that t = t∗ and i ∈ S. First, B validates e(C, g1t h1 ) = e(D, g) to clarify thevalidity of ciphertext Ctbe = (C, D, E). If validity test fails, B gives to A(i, ⊥). Otherwise, B computes the Lagrange coeﬃcients λ1 , · · · , λk−1 , λi ∈
Zp satisfying f (0) = λi f (i) + k−1
j=1 λj f (sj ) and sets

Ci =

1

( CDγ ) t−t∗

C

 k−1

j=1 λj αj

 λ1i

196

S. Arita and K. Tsurudome

and then gives to A (i, Ci ) as decryption share. (If the ciphertext is valid, it∗
must be the case that C tx+z = D. Then, we have D = C tx+z = C tx+(−t x+γ)1∗
= (C x )t−t C γ . Since t = t∗ , we get C x = (D/C γ ) t−t∗ . Then, substituting
k−1
f (0) = j=1 λj f (sj ) + λi f (i) for x, and noting Ci = C f (i) we obtain theabove expression of Ci .)4. Challenge. A outputs two same-length messages M0 and M1 . B ﬂips a∗=fair coin b ∈ {0, 1}, and responds with the challenge ciphertext Ctbe
∗
−t γ
c
c γ
c γ
t∗ c
(g , (g ) , Mb W ). (As B sets h1 = g1 g , it holds that (g ) = (h1 g1 ) .
∗Moreover, if W = e(g, g)abc , then we have Mb · W = Mb · e(g1 , g2 )c and Ctbe∗
is a valid ciphertext of Mb under P K with tag t .)5. Phase 2. A issues additional queries as in Phase 1, to which B responds as
before.
6. Guess. Eventually, A outputs a guess b . B outputs 1 if b = b , or outputs 0otherwise.
This completes the description of algorithm B, that runs in time at most τplus the time to perform O(Q + n) exponentiations and O(Q) pairing computations. By the comments in the description, it is immediate that B perfectly
simulates a stag-CCA game for A if W = e(g, g)abc . When W is a random element, the view of B is independent of the choice of b. So, Advdbdh
B,GDBDH (Λ) =stag−cca
stag−cca
|Pr[b = b ] − 1/2| = |(1/2 + AdvA,TTBE1,n,k (Λ)) − 1/2| = AdvA,TTBE1,n,k (Λ).
Second, we consider stag decryption consistency of TTBE1. Let A be an arbitrary adversary with advantage Advstag−dc
A ,TTBE1,n,k (Λ) in attacking TTBE1 in thegame of stag decryption consistency. Suppose adversary A outputs t, Ctbe , S =(μ1 = (1, C1 ), · · · , μk = (1, Ck )), S  = (μ1 = (1, C1 ), · · · , μk = (k, Ck )). If thoseshares μi in S are valid, they must satisfy e(Ci , g) = e(C, g f (i) ), so Ci = C f (i) .
kkThen, it holds that i=1 Ciλi = C i=1 λi f (i) = C x . Similarly, if the shares μi ink
λS  are valid, we have i=1 C  i i = C x . This means Combine(P K, V K, Ctbe , t, S)= Combine(P K, V K, Ctbe , t, S  ). Thus, Advstag−dc
2A ,TTBE1,n,k (Λ) = 0.
3.3

A Construction TTBE2 of Threshold Tag-Based Encryption
Scheme Based on the DLIN Assumption

Our second construction TTBE2 of threshold tag-based encryption scheme naturally expands the Kiltz’s tag-based encryption scheme [6] to the threshold setting. A secret key x1 , x2 of the Kiltz’s scheme is distributed among n secretkey shares (f1 (1), f2 (1)), · · · , (f1 (n), f2 (n)) with polynomials f1 , f2 satisfying
f (i)
f (i)
x1 = f1 (0), x2 = f2 (0). Decryption shares are of the form (C1 1 , C2 2 ).
More precisely TTBE2 is described in Figure 3.
Theorem 3. Under the DLIN assumption for GDLIN , the threshold tag-based
encryption scheme TTBE2 is stag-CCA-secure.
More precisely, for an arbitrary adversary A against stag-chosen-ciphertext
security of TTBE2 that runs in time at most τ and makes at most Q decryption

Construction of Threshold Public-Key Encryptions
Setup(n, k, Λ):(p, g, G, G1 , e) ← GDLIN (Λ);
$

197

$

x1 , x2 ← Zp ;f1 , f2 ← Zp [X] satisfying deg(f1 ) = deg(f2 ) = k − 1 and f1 (0) = x1 , f2 (0) = x2 ;1$z ← g1x1 , g2 ← z x2 , y1 , y2 ← Zp , u1 ← g1y1 , u2 ← g2y2 ;P K = (p, G, G1 , e, g1 , g2 , z, u1 , u2 ), SK = ((f1 (1), f2 (1)), · · · , (f1 (n), f2 (n)));
f (1)
f (1)
f (n)
f (n)
V K = ((v11 = g11 , v12 = g22 ), · · · , (vn1 = g11 , vn2 = g22 ));return (P K, V K, SK).
Encrypt(P K, t, M ):$r1 , r2 ← Zp , C1 ← g1r1 , C2 ← g2r2 , D1 ← (z t u1 )r1 , D2 ← (z t u2 )r2 , E ← M z r1 +r2 ;return Ctbe = (C1 , C2 , D1 , D2 , E).
ShareDec(P K, i, SKi = (f1 (i), f2 (i)), Ctbe = (C1 , C2 , D1 , D2 , ·), t):If e(C1 , z t u1 ) = e(D1 , g1 ) or e(C2 , z t u2 ) = e(D2 , g2 ) then return μi = (i, ⊥),
f (i)
f (i)
else return μi = (i, (C1 1 , C2 2 )).
ShareVf(P K, V K = ((vi1 , vi2 )), Ctbe = (C1 , C2 , ·, ·, ·), t, μi = (i, (Ci1 , Ci2 ))) :If e(Ci1 , g1 ) = e(C1 , vi1 ) or e(Ci2 , g2 ) = e(C2 , vi2 ) then return invalid, else return valid.
Combine(P K, V K, Ctbe = (·, ·, ·, ·, E), t, {μ1 = (1, (C11 , C12 )), · · · , μk = (k, (Ck1 , Ck2 ))}):
If ∃i, ShareVf(P K, V K, Ctbe , t, μi ) = invalid then return ⊥,Qelse return E/ ki=1 (Ci1 Ci2 )λi using Lagrange coeﬃcients λ1 , · · · , λkPsatisfying f1 (0) = ki=1 λi f1 (i).

Fig. 3. Threshold Tag-Based Encryption Scheme TTBE2

queries, there exists an algorithm B for the DLIN problem on GDLIN that runsin time at most τ plus the time to perform O(Q + n) exponentiations and O(Q)pairing computations and satisﬁes
dbdh
Advstag−cca
A,TTBE2,n,k (Λ) = AdvB,GDLIN (Λ).

For an arbitrary adversary A against stag decryption consistency of TTBE2, itholds that
Advstag−dc
A ,TTBE2,n,k (Λ) = 0.
Proof. First, we consider stag chosen ciphertext security of TTBE2. Let A be an
arbitrary adversary that runs in time at most τ , makes at most Q decryption
queries, and has advantage Advstag−cca
A,TTBE2,n,k (Λ) in attacking TTBE2 in the gameof stag-chosen-ciphertext security. Using the adversary A, we build an algorithm
B that solves the DLIN problem of GDLIN (Λ).
Given (Λ, p, G, G1 , e, g1 , g2 , z, g1r1 , g2r2 , W ) as input, algorithm B proceeds asfollows. (The aim of B is to distinguish two cases between W = z r1 +r2 or random.)
1. Initialization. Algorithm B invokes adversary A on input (n, k, Λ). Adversary
A outputs a target tag t∗ and a list S = {s1 , · · · , sk−1 }(⊂ {1, · · · , n}) of thek − 1 servers that it wishes to corrupt.
2. Setup. Then, B does the following:∗$(a) B picks random integers c1 , c2 ← Zp and computes u1 = z −t g1c1 , u2 =∗ cz −t g22 . (This deﬁnes implicitly as y1 = −t∗ x1 + c1 , y2 = −t∗ x2 + c2 .)B sets P K = (p, G, G1 , e, g1 , g2 , z, u1 , u2 ).

198

S. Arita and K. Tsurudome$(b) Next, B picks 2k − 2 random integers α1 , · · · , αk−1 , β1 , · · · , βk−1 ← Zp .
(We let f1 , f2 ∈ Zp [X] be two polynomials of degree k − 1 deﬁned by
f1 (0) = x1 , f1 (si ) = αi (i = 1, · · · , k − 1) and f2 (0) = x2 , f2 (si ) =βi (i = 1, · · · , k − 1). B does not know f1 , f2 .) B sets SK|S = (SKs1 =(α1 , β1 ), · · · , SKsk−1 = (αk−1 , βk−1 )).
/ S, it computes(c) For i ∈ S, B lets V Ki = (vi1 , vi2 ) = (g1αi , g2βi ). For i ∈αβvi1 = z λ0 (g1α1 )λ1 · · · (g1 k−1 )λk−1 and vi2 = z λ0 (g2β1 )λ1 · · · (g2 k−1 )λk−1 ,where λ0 , · · · , λk−1 (∈ Zp ) are the Lagrange coeﬃcients satisfying f (i) =k−1
λ0 f (0) + j=1 λj f (sj ) for degree k polynomials f . (As easily seen,
f (i)

f (i)

(vi1 , vi2 ) satisﬁes vi1 = g11 , vi2 = g22 .) B sets V K = (V K1 =(v11 , v12 ), · · · , V Kn = (vn1 , vn2 )).
(d) B gives P K, V K and SK|S to A.
3. Phase 1. A issues decryption share queries ((Ctbe , t), i) under the constraint?
that t = t∗ and i ∈ S. First, B validates e(C1 , z t u1 ) = e(D1 , g1 ) and e(C2 , z t u2 )?

= e(D2 , g2 ) to clarify validity of the ciphertext Ctbe = (C1 , C2 , D1 , D2 , E). If
validity test fails, B gives to A (i, ⊥). Otherwise, B computes the Lagrange
k−1
coeﬃcients λ1 , · · · , λk−1 , λi ∈ Zp satisfying f (0) = λi f (i) + j=1 λj f (sj )for degree k polynomials f and sets111
 ( Dc1 ) t−t∗  λi

Ci1 =

1

C
1k−1

C1

j=1 λj αj1
 ( Dc2 ) t−t∗  λi, Ci2 =

2

C
2k−1

C2 j=1λj βjand then gives to A (i, (Ci1 , Ci2 )) as decryption share. (If the ciphertext∗(t−t∗ )x1 +c1= (C1x1 )t−t C1c1 . Then,is valid, it must be the case that D1 = C1
k−1
1
since t = t∗ , we get C1x1 = (D1 /C1c1 ) t−t∗ . Substituting f1 (0) = j=1 λj f1 (sj )f (i)+ λi f1 (i) for x1 , and noting C1i = C1 1 , we obtain the above expression of
Ci1 . Similar for Ci2 .)4. Challenge. A outputs two same-length messages M0 and M1 . B ﬂips a∗=fair coin b ∈ {0, 1}, and responds with the challenge ciphertext Ctbe∗∗
(g1r1 , g2r2 , (g1r1 )c1 , (g2r2 )c2 , Mb W ). (As B sets u1 = z −t g1c1 and u2 = z −t g2c2 , it∗∗holds that (g1r1 )c1 = (u1 z t )r1 , (g2r2 )c2 = (u2 z t )r2 . Moreover, if W = z r1 +r2 ,∗is a valid ciphertext of Mb underthen we have Mb W = Mb z r1 +r2 and Ctbe
P K with tag t∗ .)5. Phase 2. A issues additional queries as in Phase 1, to which B responds as
before.
6. Guess. Eventually, A outputs a guess b . B outputs 1 if b = b , or outputs 0otherwise.
This completes the description of algorithm B, that runs in time at most τ plus
the time to perform O(Q + n) exponentiations and O(Q) pairing computations.
By the comments in the description, it is immediate that B perfectly simulatesa stag-CCA game for A if W = z r1 +r2 . When W is a random element, the view

Construction of Threshold Public-Key Encryptions

199


of B is independent of the choice b. So, Advdlin
B,GDLIN (Λ) = |Pr[b = b ] − 1/2| =stag−cca
stag−cca|(1/2 + AdvA,TTBE2,n,k (Λ)) − 1/2| = AdvA,TTBE2,n,k (Λ).

Second, we consider stag decryption consistency of TTBE2. Let A be an arbitrary adversary with advantage Advstag−dc
A ,TTBE2,n,k (Λ) in attacking TTBE2 in thegame of stag decryption consistency. Suppose adversary A outputs t, Ctbe , S =(μ1 = (1, (C11 , C12 )), · · · , μk = (k, (Ck1 , Ck2 ))), S  = (μ1 = (1, (C11, C12)), · · · ,
μk = (k, (Ck1 , Ck2 ))). If those shares μi in S are valid, they must satisfy e(Ci1 , g1 ) =
f (i)
f (i)
f (i)
f2 (i)e(C2 , g22 ), so Ci1 = C1 1 , Ci2 = C. Then, ite(C1 , g11 ), e(Ci2 , g2 ) = 
2
k
k
k
k
λi
x1
λi
i=1 λi f1 (i)i=1 λi f2 (i)holds that i=1 Ci1 = C1
= C1 and i=1 Ci2 = C2=k
λC2x2 . Similarly, if the shares μi in S  are valid, we have i=1 C  i1i = C1x1 andk λi= C2x2 . This means Combine(P K, V K, Ctbe , t, S) = Combine
i=1 C i2
(P K, V K, Ctbe , t, S  ). Thus, Advstag−dc
2A ,TTBE2,n,k (Λ) = 0.

4

Construction of Threshold Public Key Encryption
Schemes

By applying the conversion TT2TP in Section 2 to the two threshold tag-based
encryption schemes TTBE1, TTBE2 in Section 3, we obtain two threshold public
key encryption schemes TPKE1, TPKE2 that are both CCA-secure by Theorem
1, Theorem 2 and Theorem 3:
Theorem 4. Let S be a strong one-time signature.
– Under the DBDH assumption, TPKE1 = T T 2T P (TTBE1, S) is a CCAsecure threshold public key encryption scheme.
– Under the DLIN assumption, TPKE2 = T T 2T P (TTBE2, S) is a CCA-securethreshold public key encryption scheme.
Our threshold public key encryption schemes TPKE1 and TPKE2 are more simple
than the construction BBH given by Boneh, Boyen and Halevi [2]. It is because
our constructions are based on the tag-based schemes which is more simple thanthe ID-scheme used by BBH.
Instantly, Table 1 shows a comparison of eﬃciency among TPKE1, TPKE2
and BBH. The table shows the number of pairings, multi-exponentiations andregular-exponentiations required in operations of those schemes. (The entries ofTable 1. Eﬃciency Comparison among TPKE1, TPKE2 and BBH
Scheme Assumption Encrypt ShareDec ShareVf Combine reduction
pairings + [multi−exp., reg−exp.]
BBH
DBDH
1 + [1, 3] 2 + [1, 2] 2 + [0, 1] 2 + [2, 0] tight
TPKE1 DBDH
1 + [1, 3] 2 + [0, 2] 2 + [0, 0] 1 + [1, 0] tight
TPKE2 DLIN
0 + [2, 3] 4 + [0, 3] 4 + [0, 0] 0 + [1, 0] tight

200

S. Arita and K. Tsurudome

Combine do not include costs for ShareVf.) As shown, TPKE1 is more eﬃcientthan BBH. TPKE1 requires less number of exponentiation both in ShareDec,
ShareVf and Combine than BBH. On the other hand, TPKE2 has an advantagethat it is most eﬃcient both in Encrypt and Combine because it requires nocomputation of bilinear map in those operations.

5

Conclusion

In this paper, we proposed a notion of threshold tag-based encryption schemes
and showed a conversion from any stag-CCA-secure threshold tag-based encryption schemes to CCA-secure threshold public-key encryption schemes. We gave
two constructions of threshold tag-based encryption schemes and obtained two
constructions of threshold public-key encryption schemes, using that conversion.
Those schemes are non-interactive, robust, proved secure without random oracle
model and are more eﬃcient than the construction by Boneh, Boyen and Halevi [2].

References
1. Boneh, D., Boyen, X.: Eﬃcient selective-id secure identity based encryption without
random oracles. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS,
vol. 3027, pp. 223–238. Springer, Heidelberg (2004)
2. Boneh, D., Boyen, X., Halevi, S.: Chosen ciphertext secure public key thresholdencryption without random oracles. In: Pointcheval, D. (ed.) CT-RSA 2006. LNCS,
vol. 3860, pp. 226–243. Springer, Heidelberg (2006)
3. Boneh, D., Franklin, M.: Identity-based encryption from the weil pairing. In: Kilian,J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 213–229. Springer, Heidelberg (2001)
4. Canetti, R., Goldwasser, S.: An eﬃcient threshold public key cryptosystem secureagainst adaptive chosen ciphertext attack. In: Stern, J. (ed.) EUROCRYPT 1999.
LNCS, vol. 1592, pp. 90–106. Springer, Heidelberg (1999)
5. Canetti, R., Halevi, S., Katz, J.: Chosen-ciphertext security from identity-based
encryption. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS,
vol. 3027, pp. 207–222. Springer, Heidelberg (2004)
6. Kiltz, E.: Chosen-ciphertext security from tag-based encryption. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 581–600. Springer, Heidelberg (2006)
7. Sakai, R., Ohgishi, K., Kasahara, M.: Cryptosystems based on pairings. In: Proceedings of the Symposium on Cryptography and Information Security, SCIS 2000,
Japan (2000)
8. Shamir, A.: How to share a secret. Communications of the ACM, 612–613 (1979)
9. Shoup, V., Gennaro, R.: Securing threshold cryptosystems against chosen ciphertext attack. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 1–16.
Springer, Heidelberg (1998)