Paper 2017/464

On the Structure of Unconditional UC Hybrid Protocols

Mike Rosulek and Morgan Shirley

Abstract

We study the problem of secure two-party computation in the presence of a trusted setup. If there is an unconditionally UC-secure protocol for $$ that makes use of calls to an ideal $$, then we say that $$ reduces to $$ (and write $$). Some $$ are complete in the sense that all functions reduce to $$. However, almost nothing is known about the power of an incomplete $$ in this setting. We shed light on this gap by showing a characterization of $$ for incomplete $$. Very roughly speaking, we show that $$ reduces to $$ if and only if it does so by the simplest possible protocol: one that makes a single call to ideal $$ and uses no further communication. Furthermore, such simple protocols can be characterized by a natural combinatorial condition on $$ and $$. Looking more closely, our characterization applies only to a very wide class of $$, and only for protocols that are deterministic or logarithmic-round. However, we give concrete examples showing that both of these limitations are inherent to the characterization itself. Functions not covered by our characterization exhibit qualitatively different properties. Likewise, randomized, superlogarithmic-round protocols are qualitatively more powerful than deterministic or logarithmic-round ones.

Note: Revisions based on comments by TCC 2018 reviewers.