Cryptology ePrint Archive: Report 2013/419

How to Share a Lattice Trapdoor: Threshold Protocols for Signatures and (H)IBE

Rikke Bendlin and Sara Krehbiel and Chris Peikert

Abstract: We develop secure \emph{threshold} protocols for two important operations in lattice cryptography, namely, generating a hard lattice $\Lambda$ together with a ``strong'' trapdoor, and sampling from a discrete Gaussian distribution over a desired coset of $\Lambda$ using the trapdoor. These are the central operations of many cryptographic schemes: for example, they are exactly the key-generation and signing operations (respectively) for the GPV signature scheme, and they are the public parameter generation and private key extraction operations (respectively) for the GPV IBE. We also provide a protocol for trapdoor delegation, which is used in lattice-based hierarchical IBE schemes. Our work therefore directly transfers all these systems to the threshold setting.

Our protocols provide information-theoretic (i.e., statistical) security against adaptive corruptions in the UC framework, and they are private and robust against an optimal number of semi-honest or malicious parties. Our Gaussian sampling protocol is both noninteractive and efficient, assuming either a trusted setup phase (e.g., performed as part of key generation) or a sufficient amount of interactive but offline precomputation, which can be performed before the inputs to the sampling phase are known.

Category / Keywords: public-key cryptography / lattices, threshold protocols

Publication Info: This is the full version of the paper from ACNS '13

Date: received 26 Jun 2013

Contact author: cpeikert at cc gatech edu

Available format(s): PDF | BibTeX Citation

Version: 20130702:184034 (All versions of this report)

Short URL: ia.cr/2013/419

Discussion forum: Show discussion | Start new discussion