An efficient incomparable public key encryption scheme

Public keys are closely related to the identity of recipients in public key encryption setting. In privacy-sensitive applications of public key encryption, it is desirable to hide the relation between the public key and the identity of the recipient. The main functional approach in the privacy enhanced public key encryption scheme is to give anonymity of the public keys of recipients. In this case, all the users in the system are potential recipients of every ciphertext. Waters, Felten, and Sahai proposed an incomparable public key encryption scheme which guarantees the anonymity of recipients against both eavesdroppers and senders. In their scheme, all the recipients must complete the same amount of computations to identify the ciphertexts which direct to them. In this paper, we focus on reducing the number of computations for the recipients while preserving the security level of Waters et al.'s scheme. Our method is to separate the decryption process into two steps, first the recipient determines whether a ciphertext is directed to him or her, and only if the direction is correct, the recipient recovers the corresponding plaintext. This improves the efficiency of the system.