Paper 2023/310

Ramen: Souper Fast Three-Party Computation for RAM Programs

Lennart Braun, Aarhus University
Mahak Pancholi, Aarhus University
Rahul Rachuri, Aarhus University
Mark Simkin, Ethereum Foundation
Abstract

Secure RAM computation allows a number of parties to evaluate a function represented as a RAM program in a way that reveals nothing about the private inputs of the parties except from what is already revealed by the function output itself. In this work we present Ramen, which is a new protocol for computing RAM programs securely among three parties, tolerating up to one passive corruption. Ramen provides reasonable asymptotic guarantees and is concretely efficient at the same time. We have implemented our protocol and provide extensive benchmarks for various settings. Asymptotically, our protocol requires a constant number of rounds and a amortized sublinear amount of communication and computation per memory access. In terms of concrete efficiency, our protocol outperforms previous solutions. For a memory of size $2^{26}$ our memory accesses are \(30\times\) faster in the LAN and \(8.7\times\) faster in the WAN setting, when compared to the previously fastest solution by Vadapalli, Henry, and Goldberg (ePrint 2022). Due to our superior asymptotic guarantees, the efficiency gap is only widening as the memory gets larger and for this reason Ramen provides the currently most scalable concretely efficient solution for securely computing RAM programs.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
multiparty computationthree-party computationramdistributed oram
Contact author(s)
braun @ cs au dk
mahakp @ cs au dk
rahulrachuri @ fastmail com
mark simkin @ ethereum org
History
2023-03-03: approved
2023-03-02: received
See all versions
Short URL
https://ia.cr/2023/310
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/310,
      author = {Lennart Braun and Mahak Pancholi and Rahul Rachuri and Mark Simkin},
      title = {Ramen: Souper Fast Three-Party Computation for RAM Programs},
      howpublished = {Cryptology ePrint Archive, Paper 2023/310},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/310}},
      url = {https://eprint.iacr.org/2023/310}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.