Verifiable Encryption, Group Encryption, and their Applications to Separable Group Signatures and Signature Sharing Schemes

We generalize and improve the security and efficiency of the verifiable encryption scheme of Asokan et al., such that it can rely on more general assumptions, and can be proven secure without assuming random oracles. We extend our basic protocol to a new primitive called verifiable group encryption. We show how our protocols can be applied to construct group signatures, identity escrow, and signature sharing schemes from a wide range of signature, identification, and encryption schemes already in use. In particular, we achieve perfect separability for all these applications, i.e., all participants can choose their signature and encryption schemes and the keys thereof independent of each other, even without having these applications in mind.