More Efficient Digital Signatures with Tight Multi-User Security

Denis Diemert; Kai Gellert; Tibor Jager; Lin Lyu

Paper 2021/235

More Efficient Digital Signatures with Tight Multi-User Security

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

Abstract

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

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published by the IACR in PKC 2021
DOI: 10.1007/978-3-030-75248-4_1
Keywords: digital signatures tightness lossy identification schemes sequential 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
History: 2021-09-20: revised; 2021-03-02: received; See all versions
Short URL: https://ia.cr/2021/235
License: CC BY

BibTeX

@misc{cryptoeprint:2021/235,
      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},
      url = {https://eprint.iacr.org/2021/235}
}