Improved Tightly Secure (ID-Based) Signatures in the AGM

The importance of tight security has been increasingly recognised in recent years, as it helps avoid the inflation of security parameters caused by reduction loss, thereby improving efficiency. However, achieving tight security also incurs additional overhead compared to traditional designs. As a result, the efficiency gains offered by tight reductions do not always fully outweigh the costs required to realise them. This trade-off has motivated considerable efforts to design practical schemes that achieve this property without sacrificing appreciable efficiency. In this work, we show this goal can be further advanced by leveraging the Algebraic Group Model (AGM). Our first contribution is a tightly secure digital signature scheme with multi-user security against adaptive corruptions. The construction is proven in the non-programmable ROM (NPROM) + AGM and can be viewed as a simplified variant of Appendix A of AOS02 [2]. Compared to the most efficient known scheme by Diemert et al. [12], our scheme achieves a tight reduction to the DL assumption (instead of DDH), reduces the public key size from 4 to 2 elements and the computational cost from 14 to 5 exponentiations. Building on this, we further present a pairing-free identity-based signature (IBS) scheme that also achieves tight EUF-ID-CMA security under the DL assumption. Compared to the only existing IBS with the same property by Loh et al. [29], our scheme reduces the signature size from 8 to 4 elements and the computational cost from 10 to 6 exponentiations. Moreover, our security proof is in the NPROM + AGM, in contrast to prior works proven in the ROM + AGM. These results demonstrate the practical feasibility of tightly secure signature schemes in real-world applications.