International Association
for Cryptologic Research

Reductions are the workhorses of cryptography. They allow constructions of complex cryptographic primitives from simple building blocks. A prominent example is the non-interactive reduction from securely computing a ``complex" function f to securely computing a ``simple" function g via randomized encodings. Prior work equated simplicity with functions of small degree. In this work, we consider a different notion of simplicity where we require g to only take inputs from a small number of parties. In other words, we want the arity of g to be as small as possible. In more detail, we consider the problem of reducing secure computation of arbitrary functions to secure computation of functions with arity two (two is the minimal arity required to compute non-trivial functions). Specifically, we want to compute a function f via a protocol that makes parallel calls to a 2-ary function g. We want this protocol to be secure against malicious adversaries that could corrupt an arbitrary number of parties. We obtain the following results: - Negative Result: We show that there exists a degree-2 polynomial p such that no protocol that makes parallel calls to 2-ary functions can compute p with statistical security with abort. - Positive Results: We give two ways to bypass the above impossibility result. 1. Weakening the Security Notion. We show that every degree-2 polynomial can be computed with statistical privacy with knowledge of outputs (PwKO) by making parallel calls to a 2-ary function. Privacy with knowledge of outputs is weaker than security with abort. 2. Computational Security. We prove that for every function f, there exists a protocol for computing f that makes parallel calls to a 2-ary function and achieves security with abort against computationally-bounded adversaries. The security of this protocol relies on the existence of semi-honest secure oblivious transfer. - Applications: We give connections between this problem and the task of reducing the encoding complexity of Multiparty Randomized Encodings (MPRE) (Applebaum, Brakerski, and Tsabary, TCC 2018). Specifically, we show that under standard computational assumptions, there exists an MPRE where the encoder can be implemented by an NC0 circuit with constant fan-out. - Extensions: We explore this problem in the honest majority setting and give similar results assuming one-way functions. We also show that if the parties have access to 3-ary functions then we can construct a computationally secure protocol in the dishonest majority setting assuming one-way functions.