Paper 2017/464

On the Structure of Unconditional UC Hybrid Protocols

Mike Rosulek and Morgan Shirley


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 $f$ that makes use of calls to an ideal $g$, then we say that $f$ reduces to $g$ (and write $f \sqsubseteq g$). Some $g$ are complete in the sense that all functions reduce to $g$. However, almost nothing is known about the power of an incomplete $g$ in this setting. We shed light on this gap by showing a characterization of $f \sqsubseteq g$ for incomplete $g$. Very roughly speaking, we show that $f$ reduces to $g$ if and only if it does so by the simplest possible protocol: one that makes a single call to ideal $g$ and uses no further communication. Furthermore, such simple protocols can be characterized by a natural combinatorial condition on $f$ and $g$. Looking more closely, our characterization applies only to a very wide class of $f$, 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.

Available format(s)
Publication info
A minor revision of an IACR publication in TCC 2018
Contact author(s)
shirley @ cs toronto edu
2018-09-22: last of 2 revisions
2017-05-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Mike Rosulek and Morgan Shirley},
      title = {On the Structure of Unconditional UC Hybrid Protocols},
      howpublished = {Cryptology ePrint Archive, Paper 2017/464},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.