Paper 2021/1397

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

Craig Gentry, Shai Halevi, and Vadim Lyubashevsky

Abstract

Non-interactive publicly verifiable secret sharing (PVSS) schemes enables (re-)sharing of secrets 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. These 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. That application needs very large committees with thousands of parties, so the PVSS scheme in use must be efficient enough to support such large committees, in terms of both 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 often have long ciphertexts and public keys. We use the following two techniques to conserve bandwidth: 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. The resulting scheme yields $\Omega(1)$ amortized plaintext/ciphertext rate, where concretely the rate is $\approx 1/60$ for 100 parties, $\approx 1/8$ for 1000 parties, and 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/decryption of shares. Alternating between the lattice and DL settings is relatively painless, as we equate the LWE modulus with the order of the group. We also show how to reduce the the number of exponentiations in the bulletproofs by applying Johnson-Lindenstrauss-like compression to reduce the dimension of the vectors whose properties must be verified. An implementation of our PVSS with 1000 parties showed that it is feasible even at that size, and should remain so even with one or two order of magnitude increase in the committee size.

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

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Minor revision.Eurocrypt 2022
Keywords
Secure MPCVSS
Contact author(s)
craigbgentry @ gmail com
shaih @ alum mit edu
vadim lyubash @ gmail com
History
2022-05-10: last of 3 revisions
2021-10-18: received
See all versions
Short URL
https://ia.cr/2021/1397
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1397,
      author = {Craig Gentry and Shai Halevi and Vadim Lyubashevsky},
      title = {Practical Non-interactive Publicly Verifiable Secret Sharing with Thousands of Parties},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1397},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1397}},
      url = {https://eprint.iacr.org/2021/1397}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.