Paper 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. PQ-Crypto 2018
Keywords
Hash-based CryptoOne-Way FunctionsGroup SignaturesPost-Quantum Crypto
Contact author(s)
elbansarkhani @ cdc informatik tu-darmstadt de
History
2018-03-22: revised
2018-03-22: received
See all versions
Short URL
https://ia.cr/2018/274
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/274,
      author = {Rachid El Bansarkhani and Rafael Misoczki},
      title = {G-Merkle: A Hash-Based Group Signature Scheme From Standard Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2018/274},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/274}},
      url = {https://eprint.iacr.org/2018/274}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.