[Resource Topic] 2018/274: G-Merkle: A Hash-Based Group Signature Scheme From Standard Assumptions

Welcome to the resource topic for 2018/274

G-Merkle: A Hash-Based Group Signature Scheme From Standard Assumptions

Authors: Rachid El Bansarkhani, Rafael Misoczki


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.

ePrint: https://eprint.iacr.org/2018/274

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .