Cryptology ePrint Archive: Report 2021/235

More Efficient Digital Signatures with Tight Multi-User Security

Denis Diemert and Kai Gellert and 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.

Category / Keywords: digital signatures, tightness, lossy identification schemes, sequential OR-proofs

Original Publication (in the same form): IACR-PKC-2021

Date: received 1 Mar 2021

Contact author: denis diemert at uni-wuppertal de, kai gellert@uni-wuppertal de, tibor jager@uni-wuppertal de, lin lyu@uni-wuppertal de

Available format(s): PDF | BibTeX Citation

Version: 20210302:203646 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]