Paper 2018/026

Zero-Knowledge Proof of Decryption for FHE Ciphertexts

Christopher Carr, Anamaria Costache, Gareth T. Davies, Kristian Gjøsteen, and Martin Strand


Zero-knowledge proofs of knowledge and fully-homomorphic encryption are two areas that have seen considerable advances in recent years, and these two techniques are used in conjunction in the context of verifiable decryption. Existing solutions for verifiable decryption are aimed at the batch setting, however there are many applications in which there will only be one ciphertext that requires a proof of decryption. The purpose of this paper is to provide a zero-knowledge proof of correct decryption on an FHE ciphertext, which for instance could hold the result of a cryptographic election. We give two main contributions. Firstly, we present a bootstrapping-like protocol to switch from one FHE scheme to another. The first scheme has efficient homomorphic capabilities; the second admits a simple zero-knowledge protocol. To illustrate this, we use the Brakerski et al. (ITCS, 2012) scheme for the former, and Gentry's original scheme (STOC, 2009) for the latter. Secondly, we present a simple one-shot zero-knowledge protocol for verifiable decryption using Gentry's original FHE scheme.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
zero knowledgefully homomorphic encryptionverifiable decryption
Contact author(s)
martin strand @ ntnu no
2018-01-07: received
Short URL
Creative Commons Attribution


      author = {Christopher Carr and Anamaria Costache and Gareth T.  Davies and Kristian Gjøsteen and Martin Strand},
      title = {Zero-Knowledge Proof of Decryption for FHE Ciphertexts},
      howpublished = {Cryptology ePrint Archive, Paper 2018/026},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.