CryptoDB
Multiparty Garbling from OT with Linear Scaling and RAM Support
| Authors: |
|
|---|---|
| Download: | |
| Conference: | CRYPTO 2025 |
| 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. Our scheme is proved secure in the OT hybrid/random oracle model. 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 . T . log^3 T . log log T . \kappa) total bits, where \kappa is a security parameter. |
BibTeX
@inproceedings{crypto-2025-35746,
title={Multiparty Garbling from OT with Linear Scaling and RAM Support},
publisher={Springer-Verlag},
author={David Heath and Vladimir Kolesnikov and Varun Narayanan and Rafail Ostrovsky and Akash Shah},
year=2025
}