Key-and-Signature  Compact Multi-Signatures for Blockchain: A Compiler with  Realizations

Shaoquan Jiang; Dima Alhadidi; Hamid Fazli Khojir

Paper 2023/061

Key-and-Signature Compact Multi-Signatures for Blockchain: A Compiler with Realizations

Shaoquan Jiang, University of Windsor, Windsor, ON, Canada

Dima Alhadidi, University of Windsor, Windsor, ON, Canada

Hamid Fazli Khojir, University of Windsor, Windsor, ON, Canada

Abstract

Multi-signature is a protocol where a set of signatures jointly sign a message so that the final signature is significantly shorter than concatenating individual signatures together. Recently, it finds applications in blockchain, where several users want to jointly authorize a payment through a multi-signature. However, in this setting, there is no centralized authority and it could suffer from a rogue key attack where the attacker can generate his own keys arbitrarily. Further, to minimize the storage on blockchain, it is desired that the aggregated public-key and the aggregated signature are both as short as possible. In this paper, we find a compiler that converts a kind of identification (ID) scheme (which we call a linear ID) to a multi-signature so that both the aggregated public-key and the aggregated signature have a size independent of the number of signers. Our compiler is provably secure. The advantage of our results is that we reduce a multi-party problem to a weakly secure two-party problem. We realize our compiler with two ID schemes. The first is Schnorr ID. The second is a new lattice-based ID scheme, which via our compiler gives the first regular lattice-based multi-signature scheme with key-and-signature compact without a restart during signing process.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. Minor revision. IEEE Transactions on Dependable on Secure Computing
DOI: 10.1109/TDSC.2024.3410695
Keywords: Multi-signature Identification Scheme Lattice over Ring Ring-LWE Ring-SIS
Contact author(s): jiangshq @ uwindsor ca
History: 2024-07-20: last of 2 revisions; 2023-01-19: received; See all versions
Short URL: https://ia.cr/2023/061
License: CC BY

BibTeX

@misc{cryptoeprint:2023/061,
      author = {Shaoquan Jiang and Dima Alhadidi and Hamid Fazli Khojir},
      title = {Key-and-Signature  Compact Multi-Signatures for Blockchain: A Compiler with  Realizations},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/061},
      year = {2023},
      doi = {10.1109/TDSC.2024.3410695},
      url = {https://eprint.iacr.org/2023/061}
}