Threshold Cryptography as a Service (in the Multiserver and YOSO Models)

We consider large deployments of threshold cryptographic services that can run in traditional multi-server settings and, at a much larger scale, in blockchain environments. We present a set of techniques that improve performance and meet the requirements of settings with large number of servers and high rate of threshold operations. More fundamentally, our techniques enable threshold cryptographic applications to run in more challenging decentralized permissionless systems, such as contemporary blockchains. In particular, we design and implement a novel threshold solution for the recently introduced YOSO (You Only Speak Once) model. The model builds on ever changing, unpredictable committees that perform ephemeral roles in a way that evades targeting by attackers and enables virtually unlimited scalability in very large networks. Our solution allows for the maintenance of system-wide keys that can be generated, used and proactivized as needed. The specific techniques build on optimized protocols for multi-secret multidealer verifiable secret sharing and their adaptation to the YOSO model. We demonstrate the practicality of our solutions by reporting on an end-to-end implementation of a proactive re-sharing protocol in the YOSO model, showing benchmarks for committees of sizes up to 500 nodes. For traditional multi-server settings, we obtain significant speedups in settings where dealers process many secrets simultaneously (say, to generate or proactivize many keys at the same time), e.g., we show 5× improvements relative to classical Pedersen VSS for 15 servers and 50 secrets, and 48× for 500 servers and 1000 secrets.