Proofs of plaintext knowledge and group signatures incorporating same

Abstract

Systems and methods are provided for proving plaintext knowledge of a message m, encrypted in a ciphertext, to a verifier computer. The method includes, at a user computer, encrypting the message m via a predetermined encryption scheme to produce a ciphertext u, and generating a plurality l of challenges c, i=1 to l, dependent on the ciphertext u. For each challenge c, the user computer generates a cryptographic proof Πcomprising that challenge cand a zero-knowledge proof of plaintext knowledge of the message m encrypted in the ciphertext u. The user computer sends the ciphertext u and the l proofs Πto the verifier computer. Each challenge cis constrained to a predetermined challenge space C permitting identification, by searching the challenge space C, of an element c″ such that the message m can be obtained via a decryption operation using the ciphertext u, the element c″, and a decryption key of said encryption scheme.