Shorter lattice-based verifiable encryption using bimodal Gaussian

Abstract Verifiable encryption enables the decryption to be taken on properly generated ciphertexts, by making the encryptor provide a zero-knowledge proof. To meet the quantum-safe application requirements, such as key escrow, Lyubashevsky et al. proposed a one-shot verifiable encryption (LN17 scheme) based on the hardness of lattice problems. In their scheme, the FSwA-type zero-knowledge proof was obtained using rejection sampling on a discrete Gaussian distribution. In this paper, we present a construction of verifiable encryption that utilizes rejection sampling on bimodal Gaussian to get the associated zero-knowledge proof. Our new construction, while exhibiting a weaker soundness property than LN17 scheme, benefits from a smaller proof size, leading to a reduced size of the verifiable ciphertext. As for the weaker soundness property, it supports some applications such as key escrow where honestly generated verifiable ciphertexts are more useful to be decrypted out in the hope of doing some further computation tasks. We provide the efficiency comparison of the new construction by instantiating it with several sets of concrete parameters.