Cryptology ePrint Archive: Report 2016/498

Towards Tightly Secure Short Signature and IBE

Xavier Boyen and Qinyi Li

Abstract: 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).

Category / Keywords: cryptographic protocols / Tight security, pseudorandom functions, short signatures, IBE, lattices

Date: received 22 May 2016, last revised 22 Jul 2016

Contact author: qinyi li at student qut edu au

Available format(s): PDF | BibTeX Citation

Version: 20160722:080449 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]