In this work we formalize the notion of a two-party permutation correlation $$(A, B), (C, \pi )$$ s.t. $$\pi (A)=B+C$$ for a random permutation $$\pi $$ of n elements and vectors $$A,B,C\in \mathbb {F}^n$$ . 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 n elements, each of size $$\ell =\log |\mathbb {F}|$$ bits, with $$O(n\ell )$$ bit-OTs, time, communication, and only 3 rounds including setup. Similar asymptotics previously required relatively expensive public-key cryptography, e.g. Paillier or LWE. Our protocol implementation for $$n=2^{20},\ell =128$$ requires just 7 s & $$\sim 2\ell n$$ bits of communication, a respective 40 & $$1.1\times $$ 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 $$\ell $$ , i.e. the communication and number of OTs is $$O(n\log \ell )$$ . 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.(The authors grant IACR a non-exclusive and irrevocable license to distribute the article under the https://creativecommons.org/licenses/by-nc/3.0/ .)

We study verifiable outsourcing of computation in a model where the verifier has black-box access to the function being computed. We introduce the problem of oracle-aided batch verification of computation (OBVC) for a function class $$\mathcal {F}$$ . This allows a verifier to efficiently verify the correctness of any $$f \in \mathcal {F}$$ evaluated on a batch of n instances $$x_1, \ldots , x_n$$ , while only making $$\lambda $$ calls to an oracle for f (along with $$O(n \lambda )$$ calls to low-complexity helper oracles), for security parameter $$\lambda $$ . We obtain the following positive and negative results:

Fitzi, Garay, Maurer, and Ostrovsky (J. Cryptology 2005) showed that in the presence of a dishonest majority, no primitive of cardinality $$n - 1$$ is complete for realizing an arbitrary n-party functionality with guaranteed output delivery. In this work, we introduce a new 2-party primitive $$\mathcal {F}_{\textsf{SyX}}$$ (“synchronizable fair exchange”) and show that it is complete for realizing any n-party functionality with fairness in a setting where all parties are pairwise connected by instances of $$\mathcal {F}_{\textsf{SyX}}$$ . In the $$\mathcal {F}_{\textsf{SyX}}$$ -hybrid model, the two parties load $$\mathcal {F}_{\textsf{SyX}}$$ with some input, and following this, either party can trigger $$\mathcal {F}_{\textsf{SyX}}$$ with a “witness” at a later time to receive the output from $$\mathcal {F}_{\textsf{SyX}}$$ . Crucially the other party also receives output from $$\mathcal {F}_{\textsf{SyX}}$$ when $$\mathcal {F}_{\textsf{SyX}}$$ is triggered. The trigger witnesses allow us to synchronize the trigger phases of multiple instances of $$\mathcal {F}_{\textsf{SyX}}$$ , thereby aiding in the design of fair multiparty protocols. Additionally, a pair of parties may reuse a single a priori loaded instance of $$\mathcal {F}_{\textsf{SyX}}$$ in any number of multiparty protocols (involving different sets of parties). (The authors grant IACR a non-exclusive and irrevocable license to distribute the article under the https://creativecommons.org/licenses/by-nc/3.0/ ), (This work was done in part while all the authors were at MIT).

We present novel protocols to compute SQL-like join operations on secret shared database tables with non-unique join keys. Previous approaches to the problem had the restriction that the join keys of both the input tables must be unique or had quadratic overhead. Our work lifts this restriction, allowing one or both of the secret shared input tables to have an unknown and unbounded number of repeating join keys while achieving efficient O(n log n) asymptotic communication/computation and O(log n) rounds of interaction, independent of the multiplicity of the keys.

We present new semi-honest and malicious secure PSI protocols that outperform all prior works by several times in both communication and running time. Our semi-honest protocol for n = 2^20 can be performed in 0.37 seconds compared to the previous best of 2 seconds (Kolesnikov et al., CCS 2016). This can be further reduced to 0.16 seconds with 4 threads. Similarly, our protocol sends 187n bits compared to 426n bits of the next most communication-efficient protocol (Rindal et al., Eurocrypt 2021). Additionally, we apply our new techniques to the circuit PSI protocol of Rindal et al. and observe a 6x improvement in running time. These performance results are obtained by two types of improvements.