Efficient verifiable ring encryption for ad hoc groups

We propose an efficient Verifiable Ring Encryption (VRE) for ad hoc groups. VRE is a kind of verifiable encryption [16,1,4,2,8] in which it can be publicly verified that there exists at least one user, out of a designated group of n users, who can decrypt the encrypted message, while the semantic security of the message and the anonymity of the actual decryptor can be maintained. This concept was first proposed in [10] in the name of Custodian-Hiding Verifiable Encryption. However, their construction requires the inefficient cut-and-choose methodology which is impractical when implemented. We are the first to propose an efficient VRE scheme that does not require the cut-and-choose methodology. In addition, while [10] requires interaction with the encryptor when a verifier verifies a ciphertext, our scheme is non-interactive in the following sense: (1) an encryptor does not need to communicate with the users in order to generate a ciphertext together with its validity proof; and (2) anyone (who has the public keys of all users) can verify the ciphertext, without the help of the encryptor or any users. This non-interactiveness makes our scheme particularly suitable for ad hoc networks in which nodes come and go frequently as ciphertexts can be still generated and/or verified even if other parties are not online in the course. Our scheme is also proven secure in the random oracle model.