Welcome to the resource topic for 2024/1701
Title:
Secure Computation with Parallel Calls to 2ary Functions
Authors: Varun Narayanan, Shubham Vivek Pawar, Akshayaram Srinivasan
Abstract:Reductions are the workhorses of cryptography. They allow constructions of complex cryptographic primitives from simple building blocks. A prominent example is the noninteractive 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 nontrivial functions). Specifically, we want to compute a function $f$ via a protocol that makes parallel calls to 2ary functions. 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 degree2 polynomial p such that no protocol that makes parallel calls to 2ary functions can compute p with statistical security with abort.

Positive Results: We give two ways to bypass the above impossibility result.

Weakening the Security Notion. We show that every degree2 polynomial can be computed with statistical privacy with knowledge of outputs (PwKO) by making parallel calls to 2ary functions. Privacy with knowledge of outputs is weaker than security with abort.

Computational Security. We prove that for every function f, there exists a protocol for computing f that makes parallel calls to 2ary functions and achieves security with abort against computationallybounded adversaries. The security of this protocol relies on the existence of semihonest 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 \mathrm{NC}^0 circuit with constant fanout.

Extensions: We explore this problem in the honest majority setting and give similar results assuming oneway functions. We also show that if the parties have access to 3ary functions then we can construct a computationally secure protocol in the dishonest majority setting assuming oneway functions.
ePrint: https://eprint.iacr.org/2024/1701
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .