Proofs of Plaintext Knowledge and Group Signatures Incorporating Same

A computer program product for proving plaintext knowledge of a message m, encrypted in a ciphertext, to a verifier computer, said computer program product comprising a computer readable storage medium having program instructions embodied therein, the program instructions being executable by a user computer to cause the user computer to:

• encrypt the message m via a predetermined encryption scheme to produce a ciphertext u;
• generate a plurality l of challenges ci, i=1 to l, dependent on the ciphertext u;
• generate, for each challenge ci, a cryptographic proof Π2i comprising that challenge ci and a zero-knowledge proof of plaintext knowledge of the message m encrypted in the ciphertext u;
• and
• send the ciphertext u and the l proofs Π2i to the verifier computer,
• wherein each challenge ci is constrained to a predetermined challenge space C permitting identification, by searching the challenge space C, of an element ci″ such that the message m can be obtained via a decryption operation using the ciphertext u, the element ci″, and a decryption key of said encryption scheme.

A system for proving plaintext knowledge of a message m encrypted in a ciphertext, the system comprising a user computer and a verifier computer, wherein the user computer is adapted to:

• encrypt the message m via a predetermined encryption scheme to produce a ciphertext u;
• generate a plurality l of challenges ci, i=1 to l, dependent on the ciphertext u;
• generate, for each challenge ci, a cryptographic proof Π2i comprising that challenge ci and a zero-knowledge proof of plaintext knowledge of the message m encrypted in the ciphertext u;
• and
• send the ciphertext u and the l proofs Π2i to the verifier computer;
• wherein each challenge ci is constrained to a predetermined challenge space C permitting identification, by searching the challenge space C, of an element ci″ such that the message m can be obtained via a decryption operation using the ciphertext u, the element ci″, and a decryption key of said encryption scheme;
• and
• wherein the verifier computer is adapted, in response to receipt of the ciphertext u and the l proofs Π2i, to verify each proof Π2i using a public key of said encryption scheme.