September 28, 2023
Aniket Kate - Purdue University / Supra Research
Abstract. Threshold signature protocols in the literature commonly rely on broadcast channels for security and termination. Assuming (bounded) synchrony, a broadcast channel can be built over point-to-point channels between computing parties. However, for latency-sensitive applications such as distributed random beacons and threshold wallets, the Internet cannot be considered to be bounded synchronous. And, broadcast channels cannot be realized, by definition, if the network is not synchronous. Many contemporary threshold cryptographic proposals leverage blockchains as broadcast channels. However, blockchains (i.e., state machine replication (SMR) systems) only ensure that any two honest parties store the same prefix of messages in their logs. This makes SMR unsuitable as true broadcast channels. Indeed, an adversary can force an honest sender's message to not appear on a blockchain in time unless for an exorbitant broadcast time-out value. In this talk, we advocate an alternative-but-natural design approach for building threshold cryptosystems in practice. Thanks to tremendous growth in the SMR/blockchain space in the last decade, we now have SMR solutions that offer sub-second level latency and throughput above 100K msg/sec. We propose to employ these extensively available blockchains for building threshold cryptography solutions; however, we treat them as SMRs and not as broadcast channels. In the talk, we will first focus on a key gadget/primitive that is highly suitable for this setting: non-interactive (publicly verifiable) secret sharing (PVSS). We will demonstrate how the PVSS and SMR combination allows us to develop a distributed key generation setup for ECDSA, EdDSA/Schnorr, and BLS signatures. While building threshold BLS signatures will be straightforward in this setup, we will need secure multi-party computation (MPC) capability for threshold ECDSA/EdDSA signatures. In the talk, we will then present how to build these solutions using threshold additive-homomorphic encryption as a gadget along with PVSS and SMR for MPC. Finally, we will discuss solutions and challenges towards converting any broadcast-based threshold cryptosystem to one using an SMR.
[Slides] [Video]
MPTS 2023: NIST Workshop (virtual) on Multi-Party Threshold Schemes 2023