Several notions close to TPKE have been proposed in the literature. By setting the threshold to 1, a TPKE scheme becomes
indeed a broadcast encryption scheme [1,17]. In this scenario, a trusted dealer generates and privately distributes decryption
keys to n users; a sender can send a message to a dynamically chosen subset of receivers R # f1; ...; ng such that only the
users in R can decrypt the ciphertext. Fiat and Naor [17] were the first to formally explore broadcast encryption. Further
improvements [21,23] reduced the decryption key size. Dodis and Fazio [16] extended the subtree difference method into
a public-key broadcast system for a small-size public key. Wallner et al. [33] and Wong [34] independently discovered
the logical-tree-hierarchy scheme for group multicast. The parameters of the original schemes were improved in further
work [9,11,31]. Boneh et al. [6] proposed two efficient broadcast encryption schemes proven to be secure. Their basic scheme
has linear-size public keys but constant-size secret keys and ciphertexts. After a trade-off, they obtained a scheme with
Oð
ffiffiffi
n
p
Þ-size public keys, decryption keys, and ciphertexts. However, similarly to [15], they used a non-adaptive model of
security. Other contributions [7,8,20] focused on stronger adaptive security in the sense that the attacker can adaptively cor-
rupt users, as considered in this paper. Attribute-based encryption [3] is also related to the threshold decryption capability in
TPKE systems, according to the number of common attributes owned by the recipient. Ciphertext-policy based encryption
[18] can be viewed as a generalization of all the above notions, since it allows the encrypter to specify a decryption policy
and only receivers meeting the policy can decrypt. However, no joint computation is required/possible for decryption. This is
different from the usual notion of threshold cryptography, where a pool of players are required to cooperate to accomplish
the decryption operation.
1.3. Paper organization
The rest of the paper is organized as follows. In Section 2, we review the definition of TPKE systems and present a generic
conversion from a TPKE with semi-adaptive security to one with adaptive security. Section 3 proposes a basic secure TPKE
scheme with small ciphertexts and semi-adaptive security. Variants are suggested in Section 4 with fully adaptive security
and sublinear-size public/decryption keys and ciphertexts. Section 4.4 presents improvements to transmit multiple session
keys in a single session, followed by a conclusion in Section 5.
2. Modeling public-key encryption systems
We review the model of TPKE systems and then formalize the security definitions in TPKE schemes motivated by Deler-
ablée and Pointcheval [15]. We focus on standard TPKE systems where the threshold is determined by a trusted party that
we call the dealer in our definition. Compared to the definition in [15], our definition is simplified without requiring public
verifiability of the encryption and partial decryption procedures. We argue that, although this public verification might be
useful, it can be achieved modularly by employing non-interactive (zero-)knowledge proofs, and for clarity, we do not
emphasize this property in the definition of TPKE as an atomic primitive. However, we are interested in providing the stron-
ger adaptive security in TPKE systems, and, to this end, a transitional notion, i.e. semi-adaptive security, is defined.
2.1. Definition of TPKE systems
We begin by formally defining a TPKE system. Note that, for content distribution or any encryption of a long message, the
current standard technique is the KEM-DEM methodology [32], where a secret session key is generated and distributed with
public-key encryption, and then used with an appropriate symmetric cryptosystem to encrypt the content. Hence, for clarity,
we define TPKE as a key encapsulation mechanism. A TPKE system consists of the following polynomial-time algorithms:
Setup(1
k
). This algorithm is run by a trusted dealer to set up the system. It takes as input a security parameter k and it
outputs the global system parameters; the latter include n (the maximal size of a TPKE authorized receiver set) and t (the
threshold number of cooperating receivers for decryption). We denote the system parameters by
p
, which is a common
input to all the following procedures. However, we explicitly mention
p
only in the KeyGen procedure; in the other pro-
cedures it is omitted for simplicity.
KeyGen(
p
). This key generation algorithm is run by the dealer to generate the master public/secret key pair for the TPKE
system. It takes as input the system parameter
p
and it outputs hMPK,mski as the master public/secret key pair. MPK is
published and msk is kept secret by the dealer.
Join(msk,ID). This algorithm is run by a dealer to generate a decryption key for a user with identity ID. It takes as input the
master secret key msk and the identity ID of a new user who wants to join the system. It outputs the user’s keys
(UPK,udk), consisting of the user’s public key UPK for encryption, and the user’s decryption key udk for decryption. The
decryption key udk is privately given to the user, whereas UPK is widely distributed, with an authentic link to ID.
EncryptðMPK; RÞ. This algorithm is run by a sender to distribute a session key to the chosen users so that they can recover
the session key only if at least t of them cooperate. It takes as input a recipient set R # f1; ...; ng consisting of the iden-
tities (or the public keys) of the chosen users, and the TPKE master public key MPK.IfjRj 6 n, it outputs a pair hHdr,ski,
where Hdr is called the header of the session key sk. Then hHdr; Ri is sent to users in R.
B. Qin et al. / Information Sciences 210 (2012) 67–80
69