Paper 2021/1693

Verifiable Decryption for BGV

Tjerand Silde

Abstract

In this work we present a direct construction for verifiable decryption for the BGV encryption scheme by combining existing zero-knowledge proofs for linear relations and bounded values. This is one of the first constructions of verifiable decryption protocols for lattice-based cryptography, and we give a protocol that is simpler and at least as efficient as the state of the art when amortizing over many ciphertexts. To prove its practicality we provide concrete parameters, resulting in proof size of less than $44 \tau$ KB for $\tau$ ciphertexts with message space $2048$ bits. Furthermore, we provide an open source implementation showing that the amortized cost of the verifiable decryption protocol is only $76$ ms per message when batching over $\tau = 2048$ ciphertexts.

Note: This was accepted as a short paper at the workshop.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Workshop on Advances in Secure Electronic Voting 2022
Keywords
lattice cryptographyverifiable decryptionzero-knowledge
Contact author(s)
tjerand silde @ ntnu no
History
2022-05-22: last of 2 revisions
2021-12-30: received
See all versions
Short URL
https://ia.cr/2021/1693
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1693,
      author = {Tjerand Silde},
      title = {Verifiable Decryption for BGV},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1693},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1693}},
      url = {https://eprint.iacr.org/2021/1693}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.