CryptoDB
On the Structure of Unconditional UC Hybrid Protocols
| Authors: | |
|---|---|
| Download: | |
| Conference: | TCC 2018 |
| 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 f that makes use of calls to an ideal g, then we say that freduces tog (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. |
BibTeX
@inproceedings{tcc-2018-29030,
title={On the Structure of Unconditional UC Hybrid Protocols},
booktitle={Theory of Cryptography},
series={Theory of Cryptography},
publisher={Springer},
volume={11240},
pages={98-126},
doi={10.1007/978-3-030-03810-6_4},
author={Mike Rosulek and Morgan Shirley},
year=2018
}