Practical approaches to constructing public key cryptosystems secure against chosen ciphertext attacks were first initiated by Damgard and further extended by Zheng and Seberry. In this paper we first point out that in some cryptosystems proposed by Zheng and Seberry the method for adding authentication capability may fail just under known plaintext attacks. Next, we present a new method for immunizing public key cryptosystems against adaptively chosen ciphertext attacks. In the proposed immunization method, the deciphering algorithm first checks that the ciphertext is legitimate and then outputs the matching plaintext only when the check is successful. This is in contrast with the Zheng and Seberry’s methods, where the deciphering algorithm first recovers the plaintext and then outputs it only when the checking condition on it is satisfied. Such a ciphertext-based validity check will be particularly useful for an application to group-oriented cryptosystems, where almost all deciphering operations are performed by third parties, not by the actual receiver.