Paper 2018/308

On perfectly secure 2PC in the OT-hybrid model

Anat Paskin-Cherniavsky

Abstract

We initiate the study of perfect (rather than merely statistical) reductions among cryptographic primitives. For simplicity, we focus on finite functionalities. In addition to the obvious theoretical appeal of the question towards better understanding secure computation, perfect, as opposed to statistical reductions may be useful for designing MPC protocols with high concrete efficiency, achieved by eliminating the dependence on a security parameter. 1-out-of-2 bit-OT (dubbed OT) was shown to be complete for statistically secure 2PC for all functionalities [Kil88, IPS08]. Existing protocols in the OT-hybrid model only offer statistically secure with abort (efficient) protocols (requiring no further computational assumptions) for all 2PC functionalities. Disregarding efficiency requirements, all 2PC functionalities have protocols with full statistical security in this setting. As opposed to the statistical setting, it is not known whether OT is complete for perfectly secure 2PC. Furthermore, only a few sporadic examples of functionalities that have such protocols are known. On the negative side we have somewhat better understanding as implied, for instance, by the literature on fairness (for statistical security in the OT hybrid model). Quite surprisingly [IKOPS11] demonstrate that all client-server functionalities can be efficiently reduced to OT with statistical full security (no abort) in only one round. Motivated by this relative ``ease'' of client-server functionalities for statistically secure 2PC in the OT-hybrid model, we study perfect reductions to OT for this class of functions. We prove that for many client-server functions of the form $f: X\times Y\rightarrow \{0,1\}$, where server domain size $|Y|$ is larger than client domain size $|X|$, have a perfect reduction to OT. More precisely, a $g(|X|,|Y|)=\Omega(1)$-fraction of functions are perfectly reducible to OT. This fraction grows roughly as $1-exp(|X|-|Y|)$. Furthermore, our reduction is 1-round using an oracle to secure evaluation of ${\text{OT}}^l$ (as in [IKOPS11]). More generally, for $f: X\times Y\rightarrow Z$, $\Omega(1)$ of the functions with $|Y|>|X|(|Z|-1)$ are perfectly reducible to OT in 1 round. Our work leaves many open questions. The main open the question of whether all finite client-server functionalities are perfectly reducible to OT (not necessarily in one round). Another open question is whether any 2PC functionalities in the OT-hybrid model require strictly more than 1 round.

Note: The paper contained an erroneous claim that 2-out-of-5 OT falls into the class of functions that our protocol handles. This is not correct - we made a mistake evaluating the condition on this particular function. More generally, the question of devising k-out-of-n OT for k!= 1,n is left open by our result. Additionally, a few typos were fixed.