Cryptology ePrint Archive: Report 2021/970

Short Identity-Based Signatures with Tight Security from Lattices

Jiaxin Pan and Benedikt Wagner

Abstract: We construct a short and adaptively secure identity-based signature scheme tightly based on the well-known Short Integer Solution (SIS) assumption. Although identity-based signature schemes can be tightly constructed from either standard signature schemes against adaptive corruptions in the multi-user setting or a two-level hierarchical identity-based encryption scheme, neither of them is known with short signature size and tight security based on the SIS assumption. Here ``short'' means the signature size is independent of the message length, which is in contrast to the tree-based (tight) signatures. Our approach consists of two steps: Firstly, we give two generic transformations (one with random oracles and the other without) from non-adaptively secure identity-based signature schemes to adaptively secure ones tightly. Our idea extends the similar transformation for digital signature schemes. Secondly, we construct a non-adaptively secure identity-based signature scheme based on the SIS assumption in the random oracle model.

Category / Keywords: public-key cryptography / Identity-based signatures, tight security, short integer solution assumption, lattices

Original Publication (with minor differences): PQCrypto 2021

Date: received 20 Jul 2021, last revised 19 Oct 2021

Contact author: jiaxin pan at ntnu no, udpto at student kit edu

Available format(s): PDF | BibTeX Citation

Version: 20211019:152431 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]