Threshold Signatures from Inner Product Argument: Succinct, Weighted, and Multi-threshold
Sourav Das
Abstract:
Threshold signatures protect the signing key by sharing it among a group of signers so that an adversary must corrupt a threshold number of signers to be able to forge signatures. Existing threshold signatures with succinct signatures and constant verification times do not work if signers have different weights. Such weighted settings are seeing increasing importance in decentralized systems, especially in the Proof-of-Stake blockchains. This paper presents a new paradigm for threshold signatures for pairing- and discrete logarithm-based cryptosystems. Our scheme has a compact verification key consisting of only 7 group elements, and a signature consisting of 8 group elements. Verifying the signature requires 1 exponentiation and 13 bilinear pairings. Our scheme supports arbitrary weight distributions among signers and arbitrary thresholds. It requires non-interactive preprocessing after a universal powers-of-tau setup. We prove the security of our scheme in the Algebraic Group Model and implement it using golang. Our evaluation shows that our scheme achieves a comparable signature size and verification time to a standard (unweighted) threshold signature. Compared to existing multisignature schemes, our scheme has a much smaller public verification key.
Bio:
Sourav Das is a Ph.D. candidate at UIUC working with Prof. Ling Ren on applied cryptography and consensus algorithms. He is a recipient of the Chainlink Ph.D. Fellowship, a best paper runner's up at ACM CCS 2021, and the Mavis Future Faculty fellow at UIUC. He received his Bachelor's degree from IIT Delhi, where his thesis “Scaling smart contracts in Proof-of-work Blockchains" won the best undergraduate thesis award in the department.