Paper 2009/391
Threshold Decryption and Zero-Knowledge Proofs for Lattice-Based Cryptosystems
Rikke Bendlin and Ivan Damgård
Abstract
We present a variant of Regev's cryptosystem, but with a new choice of parameters. By a recent classical reduction by Peikert we prove the scheme semantically secure based on the worst-case lattice problem GapSVP. From this we construct a threshold cryptosystem which has a very efficient and non-interactive decryption protocol. We prove the threshold cryptosystem secure against passive adversaries corrupting all but one of the players, and againts active adversaries corrupting less than one third of the players. We also describe how one can build a distributed key generation protocol. In the final part of the paper, we show how one can, in zero-knowledge - prove knowledge of the plaintext contained in a given ciphertext from Regev's original cryptosystem or our variant. The proof is of size only a constant times the size of a ciphertext.
Note: This version includes a more general discussion of the choice of parameters, and how these choices are influenced by the underlying lattice assumptions.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. This is a more complete version of the paper published in the proceedings of TCC 2010.
- Contact author(s)
- rikkeb @ cs au dk
- History
- 2010-03-29: last of 5 revisions
- 2009-08-15: received
- See all versions
- Short URL
- https://ia.cr/2009/391
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2009/391,
author = {Rikke Bendlin and Ivan Damgård},
title = {Threshold Decryption and Zero-Knowledge Proofs for Lattice-Based Cryptosystems},
howpublished = {Cryptology {ePrint} Archive, Paper 2009/391},
year = {2009},
url = {https://eprint.iacr.org/2009/391}
}
