Paper 2024/1053

Stochastic Secret Sharing with $1$-Bit Shares and Applications to MPC

Benny Applebaum, Tel Aviv University
Eliran Kachlon, Tel Aviv University
Abstract

The problem of minimizing the share size of threshold secret-sharing schemes is a basic research question that has been extensively studied. Ideally, one strives for schemes in which the share size equals the secret size. While this is achievable for large secrets (Shamir, CACM '79), no similar solutions are known for the case of binary, single-bit secrets. Current approaches often rely on so-called ramp secret sharing that achieves a constant share size at the expense of a slight gap between the privacy and the correctness thresholds. In the case of single-bit shares, this leads to a large gap which is typically unacceptable. The possibility of a meaningful notion of secret sharing scheme with 1-bit shares and almost optimal threshold has been left wide open. Of special interest is the case of threshold 0.5, which is motivated by information-theoretic honest-majority secure multiparty computation (MPC). In this work, we present a new stochastic model for secret-sharing where each party is corrupted by the adversary with probability $p$, independently of the other parties, and correctness and privacy are required to hold with high probability over the choice of the corrupt parties. We present new secret sharing schemes with single-bit shares that tolerate any constant corruption probability $p<0.5$. Our construction is based on a novel connection between such stochastic secret-sharing schemes and error-correcting codes that achieve capacity over the binary erasure channel. Our schemes are linear and multiplicative. We demonstrate the usefulness of the model by using our new schemes to construct MPC protocols with security against an adversary that passively corrupts an arbitrary subset of $0.499n$ of the parties, where the online communication per party consists of a single bit per AND gate and zero communication per XOR gate. Unlike competing approaches for communication-efficient MPC, our solution is applicable even in a real-time model in which the parties should compute a Boolean circuit whose gates arrive in real-time, one at a time, and are not known in advance.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in CRYPTO 2024
Keywords
Secret SharingMPC
Contact author(s)
benny applebaum @ gmail com
elirn chalon @ gmail com
History
2024-06-30: approved
2024-06-28: received
See all versions
Short URL
https://ia.cr/2024/1053
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1053,
      author = {Benny Applebaum and Eliran Kachlon},
      title = {Stochastic Secret Sharing with $1$-Bit Shares and Applications to {MPC}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1053},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1053}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.