Cryptology ePrint Archive: Report 2018/274
G-Merkle: A Hash-Based Group Signature Scheme From Standard Assumptions
Rachid El Bansarkhani and Rafael Misoczki
Abstract: Hash-based signature schemes are the most promising cryptosystem candidates in a post-quantum world, but offer little structure to enable more sophisticated constructions such as group signatures.
Group signatures allow a group member to anonymously sign messages on behalf of the whole group (as needed for anonymous remote attestation).
In this work, we introduce G-Merkle, the first (stateful) hash-based group signature scheme.
Our proposal relies on minimal assumptions, namely the existence of one-way functions, and offers performance equivalent to the Merkle single-signer setting. The public key size (as small as in the single-signer setting) outperforms all other post-quantum group signatures. Moreover, for $N$ group members issuing at most $B$ signatures each, the size of a hash-based group signature is just as large as a Merkle signature with a tree composed by $N\cdot B$ leaf nodes. This directly translates into fast signing and verification engines.
Different from lattice-based counterparts, our construction does not require any random oracle. Note that due to the randomized structure of our Merkle tree, the signature authentication paths are pre-stored or deduced from a public tree, which seems a requirement hard to circumvent. To conclude, we present implementation results to demonstrate the practicality of our proposal.
Category / Keywords: public-key cryptography / Hash-based Crypto, One-Way Functions, Group Signatures, Post-Quantum Crypto
Original Publication (in the same form): PQ-Crypto 2018
Date: received 16 Mar 2018, last revised 22 Mar 2018
Contact author: elbansarkhani at cdc informatik tu-darmstadt de
Available format(s): PDF | BibTeX Citation
Version: 20180322:191400 (All versions of this report)
Short URL: ia.cr/2018/274
[ Cryptology ePrint archive ]