Paper 2016/498

Towards Tightly Secure Short Signature and IBE

Xavier Boyen and Qinyi Li


Constructing short signatures with tight security from standard assumptions is a long-standing open problem. We present an adaptively secure, short (and stateless) signature scheme, featuring a constant security loss relative to a conservative hardness assumption, Short Integer Solution (SIS), and the security of a concretely instantiated pseudorandom function (PRF). This gives a class of tightly secure short lattice signature schemes whose security is based on SIS and the underlying assumption of the instantiated PRF. Our signature construction further extends to give a class of tightly and adaptively secure ``compact" Identity-Based Encryption (IBE) schemes, reducible with constant security loss from Regev's vanilla Learning With Errors (LWE) hardness assumption and the security of a concretely instantiated PRF. Our approach is a novel combination of a number of techniques, including Katz and Wang signature, Agrawal et al.\ lattice-based secure IBE, and Boneh et al.\ key-homomorphic encryption. Our results, at the first time, eliminate the dependency between the number of adversary's queries and the security of short signature/IBE schemes in the context of lattice-based cryptography. They also indicate that tightly secure PRFs (with constant security loss) would imply tightly, adaptively secure short signature and IBE schemes (with constant security loss).

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Tight securitypseudorandom functionsshort signaturesIBElattices
Contact author(s)
qinyi li @ student qut edu au
2016-07-22: revised
2016-05-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Xavier Boyen and Qinyi Li},
      title = {Towards Tightly Secure Short Signature and IBE},
      howpublished = {Cryptology ePrint Archive, Paper 2016/498},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.