Welcome to the resource topic for 2025/2135
Title:
Robust Elections and More: Fast MPC in the Preprocessing Model
Authors: Charanjit S. Jutla, Nathan Manohar, Arnab Roy
Abstract:In this paper, we present an MPC protocol in the preprocessing model with essentially the same concrete online communication and rounds as the state-of-the-art MPC protocols such as online-BGW (with precomputed Beaver tuples) for t < n/3 malicious corruptions. However, our protocol additionally guarantees robustness and correctness against up to t < n/2 malicious corruptions while the privacy threshold remains at n/3. This is particularly useful in settings (e.g. commodity/stock market auctions, national elections, IACR elections) where it is paramount that the correct outcome is certified, while maintaining the best possible online speed. In addition, this honest-majority correctness allows us to use optimistic Berlekamp-Welch decoding in contrast to BGW. Moreover, just like online-BGW, our protocol is responsive until a final attestation phase.
We also give a complementary verifiable input-sharing scheme for the multi-client distributed-server setting which satisfies both robustness and correctness against up to t < n/2 malicious servers. This is accomplished by having the servers first run a preprocessing phase that does not involve the clients. The novelty of this input-sharing scheme is that a client only interacts for one round, and hence need not be online, which, again, is highly desirable in applications such as elections/auctions.
We prove our results in the universally-composable model with statistical security against static corruptions. Our protocol is achieved by combining global authenticators of SPDZ with an augmented Reed-Solomon code in a novel manner. This augmented code enables honest-majority decoding of degree n/2 Reed-Solomon codes. Our particular augmentation (often referred to as robust sharing) has the additional property that the preprocessing phase can generate this augmented sharing with a factor n speedup over prior information-theoretic robust sharing schemes.
ePrint: https://eprint.iacr.org/2025/2135
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .