Pseudorandom Correlation Functions (PCFs) allow two parties, given correlated evaluation keys, to locally generate arbitrarily many pseudorandom correlated strings, e.g. Oblivious Transfer (OT) correlations, which can then be used by the two parties to jointly run secure computation protocols. In this work, we provide a novel and simple approach for constructing PCFs for OT correlation, by relying on constrained pseudorandom functions for a class of constraints containing a weak pseudorandom function (wPRF). We then show that tweaking the Naor-Reingold pseudorandom function and relying on low-complexity pseudorandom functions allow us to instantiate our paradigm. We further extend our ideas to obtain efficient public-key PCFs, which allow the distribution of correlated keys between parties to be non-interactive: each party can generate a pair of public/secret keys, and any pair of parties can locally derive their correlated evaluation key by combining their secret key with the other party’s public key. In addition to these theoretical contributions, we detail various optimizations and provide concrete instantiations of our paradigm relying on the Boneh-Ishai-Passelègue-Sahai-Wu wPRF and the Goldreich-Applebaum-Raykov wPRF. Putting everything together, we obtain public-key PCFs with a throughput of 15k–40k OT/s, which is of a similar order of magnitude to the state-of-the-art interactive PCFs and about 4 orders of magnitude faster than state-of-the art public-key PCFs. As a side result, we also show that public-key PCFs can serve as a building block to construct reusable designated-verifier non-interactive zero-knowledge proofs (DV-NIZK) for NP. Combined with our instantiations, this yields simple and efficient reusable DV-NIZKs for NP in pairing-free groups.

We consider the graph-theoretic problem of removing (few) nodes from a directed acyclic graph in order to reduce its depth. While this problem is intractable in the general case, we provide a variety of algorithms in the case where the graph is that of a circuit of fan-in (at most) two, and explore applications of these algorithms to secure multiparty computation with low communication. Over the past few years, a paradigm for low-communication secure multiparty computation has found success based on decomposing a circuit into low-depth “chunks”. This approach was however previously limited to circuits with a “layered” structure. Our graph-theoretic approach extends this paradigm to all circuits. In particular, we obtain the following contributions: Fractionally linear-communication MPC in the correlated randomness model. We provide an N -party protocol for computing an n -input, m -output \(\mathbb {F}\) -arithmetic circuit with s internal gates (over any basis of binary gates) with communication complexity \((\frac{2}{3}s + n + m)\cdot N\cdot \log |\mathbb {F}|\) , which can be improved to \(((1+\epsilon )\cdot \frac{2}{5}s+n+m)\cdot N\cdot \log |\mathbb {F}|\) (at the cost of increasing the computational overhead from a small constant factor to a large one). Previously, comparable protocols either used more than \(s\cdot N\cdot \log |\mathbb {F}|\) bits of communication, required super-polynomial computation, were restricted to layered circuits, or tolerated a sub-optimal corruption threshold. Sublinear-Communication MPC. Assuming the existence of N -party Homomorphic Secret Sharing for logarithmic depth circuits (respectively doubly logarithmic depth circuits), we show there exists sublinear-communication secure N -party computation for all \(\log ^{1+o(1)}\) -depth (resp. \((\log \log )^{1+o(1)}\) -depth) circuits. Previously, this result was limited to \((\mathcal {O}(\log ))\) -depth (resp. \((\mathcal {O}(\log \log ))\) -depth) circuits, or to circuits with a specific structure ( e.g. layered). The \(\boldsymbol{{N\atopwithdelims ()1}}\) -OT complexity of MPC. We introduce the “ \(N\atopwithdelims ()1\) -OT complexity of MPC ” of a function f , denoted \(C_N(f)\) , as the number of oracle calls required to securely compute f in the \(N\atopwithdelims ()1\) -OT hybrid model. We establish the following upper bound: for every \(N\ge 2\) , \(C_N(f) \le (1+g(N))\cdot \frac{2 |f|}{5}\) , where g ( N ) is an explicit vanishing function. We also obtain additional contributions to reducing the amount of bootstrapping for fully homomorphic encryption, and to other types of sublinear-communication MPC protocols such as those based on correlated symmetric private information retrieval.