Efficient Threshold Public Key Encryption from the Computational Bilinear Diffie-Hellman Assumption

In this paper, we show the first efficient threshold public-key encryption (TPKE) scheme under the difficulty of search problems. More specifically, our TPKE scheme simultaneously achieves: (1) chosen ciphertext security (CCA security) under the computational bilinear Diffie-Hellman (CBDH) assumption in the standard model; (2) re-splittability, which is a useful property that makes partial secret keys refreshable; and (3) O(√κ )-bit ciphertexts, public keys, and secret keys, where κ is a security parameter. Most previous CCA-secure TPKE schemes rely on decisional complexity assumptions or random oracles. Although there exist CCA-secure TPKE schemes under the difficulty of search problems, all such schemes are inefficient or work over small plaintext spaces. Technically, we begin with a direct construction of a threshold identity-based key encapsulation mechanism (TIB-KEM) with a weak security notion. Then, we transform the weakly-secure TIB-KEM into a CCA-secure TPKE scheme via the tag-KEM/DEM approach.