Paper 2021/235

More Efficient Digital Signatures with Tight Multi-User Security

Denis Diemert, Kai Gellert, Tibor Jager, and Lin Lyu


We construct the currently most efficient signature schemes with tight multi-user security against adaptive corruptions. It is the first generic construction of such schemes, based on lossy identification schemes (Abdalla etal; JoC 2016), and the first to achieve strong existential unforgeability. It also has significantly more compact signatures than the previously most efficient construction by Gjosteen and Jager (CRYPTO 2018). When instantiated based on the decisional Diffie-Hellman assumption, a signature consists of only three exponents. We propose a new variant of the generic construction of signatures from sequential OR-proofs by Abe, Ohkubo, and Suzuki (ASIACRYPT 2002) and Fischlin, Harasser, and Janson (EUROCRYPT 2020). In comparison to Fischlin etal, who focus on constructing signatures in the non-programmable random oracle model (NPROM), we aim to achieve tight security against adaptive corruptions, maximize efficiency, and to directly achieve strong existential unforgeability (also in the NPROM). This yields a slightly different construction and we use slightly different and additional properties of the lossy identification scheme. Signatures with tight multi-user security against adaptive corruptions are a commonly-used standard building block for tightly-secure authenticated key exchange protocols. We also show how our construction improves the efficiency of all existing tightly-secure AKE protocols.

Note: Update for DOI and clickable references

Available format(s)
Public-key cryptography
Publication info
Published by the IACR in PKC 2021
digital signaturestightnesslossy identification schemessequential OR-proofs
Contact author(s)
denis diemert @ uni-wuppertal de
kai gellert @ uni-wuppertal de
tibor jager @ uni-wuppertal de
lin lyu @ uni-wuppertal de
2021-09-20: revised
2021-03-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Denis Diemert and Kai Gellert and Tibor Jager and Lin Lyu},
      title = {More Efficient Digital Signatures with Tight Multi-User Security},
      howpublished = {Cryptology ePrint Archive, Paper 2021/235},
      year = {2021},
      doi = {10.1007/978-3-030-75248-4_1},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.