Welcome to the resource topic for 2025/444
Title:
Multiparty Garbling from OT with Linear Scaling and RAM Support
Authors: David Heath, Vladimir Kolesnikov, Varun Narayanan, Rafail Ostrovsky, Akash Shah
Abstract:State-of-the-art protocols that achieve constant-round secure multiparty computation currently present a trade-off: either consume an amount of communication that scales quadratically in the number of parties, or achieve better asymptotics at the cost of high constant factors (e.g. schemes based on LPN or DDH).
We construct a constant-round MPC protocol where communication scales linearly in the number of parties n. Our construction relies only on OT and RO, and it leverages packed secret sharing. Due to building on simple primitives, our protocol offers concrete improvement over asymptotically-efficient LPN-based schemes. We consider security in the presence of a dishonest majority where the malicious (with abort) adversary corrupts an arbitrary constant fraction of parties.
By leveraging tri-state circuits (Heath et al. Crypto 2023), we extend our protocol to the RAM model of computation. For a RAM program that halts within T steps, our maliciously-secure protocol communicates O(n \cdot T \log^3 T \log \log T \cdot \kappa) total bits, where \kappa is a security parameter.
ePrint: https://eprint.iacr.org/2025/444
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 .