Paper 2021/558

Verifiable Decryption in the Head

Kristian Gjøsteen, Thomas Haines, Johannes Müller, Peter Rønne, and Tjerand Silde


In this work we present a new approach to verifiable decryption which converts a 2-party passively secure distributed decryption protocol into a 1-party proof of correct decryption. To introduce our idea, we present a toy example for an ElGamal distributed decryption protocol that we also give a machine checked proof of, in addition to applying our method to lattices. This leads to an efficient and simple verifiable decryption scheme for lattice-based cryptography, especially for large sets of ciphertexts; it has small size and lightweight computations as we reduce the need of zero-knowledge proofs for each ciphertext. We believe the flexibility of the general technique is interesting and provides attractive trade-offs between complexity and security, in particular for the interactive variant with smaller soundness. Finally, the protocol requires only very simple operations, making it easy to correctly and securely implement in practice. We suggest concrete parameters for our protocol and give a proof of concept implementation, showing that it is highly practical.

Note: This is the full version of the paper accepted at ACISP 2022.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. Australasian Conference on Information Security and Privacy 2022
verifiable decryptiondistributed decryptionlattice-based cryptoMPC-in-the-Headzero-knowledge proofimplementation
Contact author(s)
kristian gjosteen @ ntnu no
thomas haines @ ntnu no
johannes mueller @ uni lu
peter roenne @ uni lu
tjerand silde @ ntnu no
2022-05-22: revised
2021-05-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Kristian Gjøsteen and Thomas Haines and Johannes Müller and Peter Rønne and Tjerand Silde},
      title = {Verifiable Decryption in the Head},
      howpublished = {Cryptology ePrint Archive, Paper 2021/558},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.