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