Embodiments of the present invention may provide the capability for performing public-key encryption with proofs of plaintext knowledge using a lattice-based scheme that provides improved efficiency over conventional techniques. For example, in an embodiment, a computer-implemented method of verifying encryption may comprise generating a ciphertext, derived from a plaintext, via an encryption scheme, proving validity of the ciphertext, wherein the proof includes at least one challenge value, and using a decryption procedure that recovers a plaintext by choosing at least one additional challenge value at random from a challenge space.