You are looking at a specific version 20201129:190737 of this paper. See the latest version.

Paper 2020/1478

Robust Subgroup Multi-Signatures for Consensus

David Galindo and Jia Liu

Abstract

Multi-signatures are used to attest that a fixed collection of $n$ parties, represented by their respective public keys, have all signed a given message. An emerging application of multi-signatures is to be found in consensus protocols to attest that a qualified subset of a global set of $n$ validators have reached agreement. In this paper, we point out that the traditional security model for multi-signatures is insufficient for this new application, as it assumes that every party in the set participates in the multi-signature computation phase and is honest. None of these assumptions hold in the typical adversarial scenarios in consensus protocols (aka. byzantine agreement). We address this by introducing a new multi-signature variant called robust subgroup multi-signatures, whereby any eligible subgroup of signers from the global set can produce a multi-signature on behalf of the group, even in the presence of a byzantine adversary. We provide syntax and security definitions for the new variant. We argue that existing unforgeability security proofs for multi-signatures do not carry over to the consensus setting; a consequence of this observation is that many multi-signature based consensus protocols lack a rigorous security proof for correctness. To remedy this we propose several constructions which we prove secure under widely held cryptographic assumptions using our newly introduced formal definitions and also improve upon multi-signature computation time. Finally, we report on benchmarks from a proof-of-concept implementation.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
multi-signaturesblockchainconsensus protocolsaggregate signaturesforking lemma
Contact author(s)
d galindo @ bham ac uk
jia liu @ fetch ai
History
2020-11-29: received
Short URL
https://ia.cr/2020/1478
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.