Efficient Permutation Correlations and Batched Random Access for Two-Party Computation
Stanislav Peceny, Georgia Institute of Technology
Srinivasan Raghuraman, Visa Research & Massachusetts Institute of Technology
Peter Rindal, Visa Research
Harshal Shah, Visa Research
Abstract
In this work we formalize the notion of a two-party permutation correlation s.t. for a random permutation of elements and vectors . This correlation can be viewed as an abstraction and generalization of the Chase et al. (Asiacrypt 2020) share translation protocol. We give a systematization of knowledge for how such a permutation correlation can be derandomized to allow the parties to perform a wide range of oblivious permutations of secret-shared data. This systematization immediately enables the translation of various popular honest-majority protocols to be efficiently instantiated in the two-party setting, e.g. collaborative filtering, sorting, database joins, graph algorithms, and many more.
We give two novel protocols for efficiently generating a random permutation correlation. The first uses MPC-friendly PRFs to generate a correlation of elements, each of size bits, with bit-OTs, time, communication, and only three rounds. Similar asymptotics previously required relatively expensive public-key cryptography, e.g. Paillier or LWE. Our protocol implementation for requires just 7 seconds & bits of communication, a respective 40 & improvement on the LWE solution of Juvekar at al. (CCS 2018). The second protocol is based on pseudo-random correlation generators and achieves an overhead that is sublinear in the string length , i.e. the communication and number of OTs is . The overhead of the latter protocol has larger hidden constants, and therefore is more efficient only when long strings are permuted, e.g. in graph algorithms.
Finally, we present a suite of highly efficient protocols based on permutations for performing various batched random access operations. These include the ability to extract a hidden subset of a secret-shared list. More generally, we give ORAM-like protocols for obliviously reading and writing from a list in a batched manner. We argue that this suite of batched random access protocols should be a first class primitive in the MPC practitioner's toolbox.
@misc{cryptoeprint:2024/547,
author = {Stanislav Peceny and Srinivasan Raghuraman and Peter Rindal and Harshal Shah},
title = {Efficient Permutation Correlations and Batched Random Access for Two-Party Computation},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/547},
year = {2024},
url = {https://eprint.iacr.org/2024/547}
}
Note: In order to protect the privacy of readers, eprint.iacr.org
does not use cookies or embedded third party content.