Paper 2021/1397

Practical Non-interactive Publicly Verifiable Secret Sharing with Thousands of Parties

Craig Gentry and Shai Halevi and Vadim Lyubashevsky

Abstract

Non-interactive publicly verifiable secret sharing (PVSS) schemes allow parties to re-share a secret in a decentralized setting in the presence of malicious parties. A recently proposed application of PVSS schemes is to enable permissionless proof-of-stake blockchains to ``keep a secret" via a sequence of committees that share that secret. Such committees can use the secret to produce signatures on the blockchain's behalf, or to disclose hidden data conditioned on consensus that some event has occurred. Such a setting may involve thousands of parties, so the PVSS scheme that it uses must be very efficient, both in computation and communication. Yet, previous PVSS schemes have large proofs and/or require many exponentiations over large groups. We present a non-interactive PVSS scheme in which the underlying encryption scheme is based on the learning with errors (LWE) problem. While lattice-based encryption schemes are very fast, they have issues with bandwidth (long ciphertexts and public keys). We deal with the bandwidth issue in two ways. First, we adapt the Peikert-Vaikuntanathan-Waters (PVW) encryption scheme to the multi-receiver setting so that the bulk of the parties' keys is a common random string, and so that we get good amortized communication: $\Omega(1)$ plaintext/ciphertext rate (rate $\approx 1/60$ for 100 parties, $\approx 1/8$ for 1000 parties, approaching 1/2 as the number of parties grows). Second, we use bulletproofs over a DL-group of order about 256 bits to get compact proofs of correct encryption of shares. Switching from the lattice setting to the DL setting is relatively painless, as we equate the LWE modulus with the order of the group, and apply dimension reduction to vectors before the switch to minimize the number of exponentiations in the bulletproof. An implementation of our PVSS for 1000 parties showed that it's quite practical, and should remain so with up to a two order of magnitude increase in the group size.

Note: A proof-of-concept implementation in C++ is available under MIT license from https://github.com/shaih/cpp-lwevss