Efficient Permutation Correlations and Batched Random Access for Two-Party Computation

ePrint Report: Efficient Permutation Correlations and Batched Random Access for Two-Party Computation

Stanislav Peceny, Srinivasan Raghuraman, Peter Rindal, Harshal Shah

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. …

access computation correlation eprint report notion party peter random report utility work