Threshold Decryption and Zero-Knowledge Proofs for Lattice-Based Cryptosystems

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperConference articleResearchpeer-review

  • Department of Computer Science
We present a variant of Regev's cryptosystem first presented in [Reg05], 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 the public key.
Original languageEnglish
Book seriesLecture Notes in Computer Science
Pages (from-to)201-218
Number of pages18
Publication statusPublished - 2010
EventTheory of Cryptography Conference. TCC 2010 - Zürich, Switzerland
Duration: 9 Feb 201011 Feb 2010
Conference number: 7


ConferenceTheory of Cryptography Conference. TCC 2010

Bibliographical note

Title of the vol.: Theory of Cryptography : 7th Conference, TCC 2010, Zurich, Switzerland, February 9-11, 2010 : Proceedings / ed. by Daniele Micciancio.
ISBN: 3642117988; 9783642117985

See relations at Aarhus University Citationformats

ID: 19611024