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 present a novel construction that enables two parties to securely train a logistic regression model on private secret-shared data. Our goal is to minimize online communication and round complexity, while still allowing for an efficient offline phase. As part of our construction, we develop many building blocks of independent interest. These include a new ap-proximation technique for the sigmoid function that results in a secure protocol with better communication, protocols for secure powers evaluation and secure spline computation on fixed-point values, and a new comparison protocol that optimizes online communication. We also present a new two-party protocol for generating keys for distributed point functions (DPFs) over arithmetic sharing, where previous constructions do this only for Boolean outputs. We implement our protocol in an end-to-end system and benchmark its efficiency. We can securely evaluate a batch of 103sigmoids with$\approx 0.5$MB of online communication, 4 online rounds, and$\approx 1.6$seconds of online time over WAN. This is$\approx 30\times$less in online communication,$\approx 31\times$fewer online rounds, and$\approx 5.5\times$less online time than the well-known MP-SPDZ's protocol. Our system can train a logistic regression model over 6 epochs and a database containing 70, 000 samples and 15 features with 208.09 MB of online communication and 9.68 minutes of online time. We compare our logistic regression training against MP-SPDZ over a synthetic dataset of 1000 samples and 10 features and show an improvement of$\approx 130\times$in online communication and ≈ 4.75× in online time over WAN. We converge to virtually the same model as plaintext in all cases. We open-source our system and include extensive tests.

In MPC, we usually represent programs as circuits. This is a poor fit for programs that use complex control flow, as it is costly to compile control flow to circuits. This motivated prior work to emulate CPUs inside MPC. Emulated CPUs can run complex programs, but they introduce high overhead due to the need to evaluate not just the program, but also the machinery of the CPU, including fetching, decoding, and executing instructions, accessing RAM, etc.