Welcome to the resource topic for 2024/547
Title:
Efficient Permutation Correlations and Batched Random Access for Two-Party Computation
Authors: Stanislav Peceny, Srinivasan Raghuraman, Peter Rindal, Harshal Shah
Abstract:In this work we define the notion of a permutation correlation (\pi,A,B,C) s.t. \pi(A)=B+C for a random permutation \pi of n elements and vectors A,B,C\in \mathbb{F}^n. We demonstrate the utility of this correlation for a wide range of applications. The correlation can be derandomized to obliviously shuffle a secret-shared list, permute a secret-shared list by a secret-shared permutation, and more. Similar techniques have emerged as a popular building block for the honest majority protocols when efficient batched random access is required, e.g. collaborative filtering, sorting, database joins, graph algorithms, and many more. We present the highly flexible notion of permutation correlation and argue that it should be viewed as a first class primitive in the MPC practitioner’s toolbox.
We give two novel protocols for efficiently generating a random permutation correlation. The first makes use of recent advances in MPC-friendly PRFs to obtain a protocol requiring O(n\ell) OTs/time and constant rounds to permute n \ell-bit strings. Unlike the modern OT extension techniques we rely on, this was previously only achievable from relatively more expensive public-key cryptography, e.g. Paillier or LWE. We implement this protocol and demonstrate that it can generate a correlation for n=2^{20},\ell=128 in 19 seconds and \sim2\ell n communication, a 15 & 1.1\times improvement over 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 \emph{sublinear} in the string length \ell, i.e. the communication and number of OTs is O(n\log \ell). The latter protocol is ideal for the setting when you need to repeatedly permute secret-shared data by the same permutation, e.g. in graph algorithms.
Finally, we present a suite of highly efficient protocols for performing various batched random access operations. These include a class of protocols we refer to as \emph{extraction}, which allow a user to \emph{mark} a subset of X and have this subset obliviously extracted into an output list. Additionally, the parties can specify an \emph{arbitrary} selection function \sigma:[n]\rightarrow[n] and obtain shares of \sigma(X)=(X_{\sigma(1)},\ldots,X_{\sigma(n)}) from X. We implement these protocols and report on their performance.
ePrint: https://eprint.iacr.org/2024/547
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 .