Public key encryption methods and apparatus are provided for encrypting secret data under a public key in a data processing system (1). The secret data is provided as a message (m) comprising at least one element of a pair of base groups G1, G2 satisfying a bilinear map e: G1 x G2? GT where GT is a target group. The message (m) is encrypted using said public key to produce an encrypted message (c). A consistency component (v) is generated using the encrypted message (c) and said bilinear map whereby the consistency component (v) permits validation of the encrypted message without revealing the encrypted message. The output ciphertext (ct) comprises the encrypted message (c) and the consistency component (v).