We present a new unifying framework for constructing non-interactive threshold encryption and signature schemes, as well as broadcast encryption schemes, and in particular, derive several new cryptosystems based on hardness of factoring, including:
a threshold signature scheme (in the random oracle model) that supports ad-hoc groups (i.e., exponential number of identities and the set-up is independent of the total number of parties) and implements the standard Rabin signature;
a threshold encryption scheme that supports ad-hoc groups, where encryption is the same as that in the Blum-Goldwasser cryptosystem and therefore more efficient than RSA-based implementations;
a CCA-secure threshold encryption scheme in the random oracle model;
a broadcast encryption scheme (more precisely, a revocation cryptosystem) that supports ad-hoc groups, whose complexity is comparable to that of the Naor-Pinkas scheme; moreover, we provide a variant of the construction that is CCA-secure in the random oracle model.
Our framework rests on a new notion of
threshold extractable hash proofs
. The latter can be viewed as a generalization of the extractable hash proofs, which are a special kind of non-interactive zero-knowledge proof of knowledge.