Paper 2013/419

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

Rikke Bendlin, Sara Krehbiel, and Chris Peikert


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.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. This is the full version of the paper from ACNS '13
latticesthreshold protocols
Contact author(s)
cpeikert @ cc gatech edu
2013-07-02: received
Short URL
Creative Commons Attribution


      author = {Rikke Bendlin and Sara Krehbiel and Chris Peikert},
      title = {How to Share a Lattice Trapdoor: Threshold Protocols for Signatures and (H)IBE},
      howpublished = {Cryptology ePrint Archive, Paper 2013/419},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.