On Lower Bounds and Size Reduction for Correlated Randomness in Secure Two-party Computation

Bar Alon, Olga V. Nissenbaum, Eran Omri +2 more

Yuval Ishai, Eyal Kushilevitz Z, Sigurd Meldgaard +2 more

Keitaro Hiwatashi, Koji Nuida

Secure two-party computation is a cryptographic tool that enables two parties to compute a function jointly without revealing their inputs. It is known that any function can be realized in the correlated randomness (CR) model, where a trusted dealer distributes input-independent CR to the parties beforehand. Sometimes we can construct more efficient secure two-party protocol for a function g than that for a function f, where g is a restriction of f. However, it is not known in which case we can construct more efficient protocol for domain-restricted function. In this paper, we focus on the size of CR. We prove that we can construct more efficient protocol for a domain-restricted function when there is a “good” structure in CR space of a protocol for the original function, and show a unified way to construct a more efficient protocol in such case. In addition, we show two applications of the above result: The first application shows that some known techniques of reducing CR size for domain-restricted function can be derived in a unified way, and the second application shows that we can construct more efficient protocol than an existing one using our result.

Severin Winkler

We provide bounds on the efficiency of secure one-sided output two-party computation of arbitrary finite functions from trusted distributed randomness in the statistical case. From these results we derive bounds on the efficiency of protocols that use different variants of OT as a black-box. When applied to implementations of OT, these bounds generalize most known results to the statistical case. Our results hold in particular for transformations between a finite number of primitives and for any error. In the second part we study the efficiency of quantum protocols implementing OT. While most classical lower bounds for perfectly secure reductions of OT to distributed randomness still hold in the quantum setting, we present a statistically secure protocol that violates these bounds by an arbitrarily large factor. We then prove a weaker lower bound that does hold in the statistical quantum setting and implies that even quantum protocols cannot extend OT. Finally, we present two lower bounds for reductions of OT to commitments and a protocol based on string commitments that is optimal with respect to both of these bounds.

Stefan Wolf, Jürg Wullschleger

Since oblivious transfer, a primitive of paramount importance in secure two- and multiparty computation, cannot be realized in an unconditionally secure way for both parties from scratch, reductions to weak information-theoretic primitives as well as between different variants of the functionality are of great interest. In this context, various monotones-quantities that cannot be increased by any protocol-are introduced and then used to derive lower bounds on the possibility and efficiency of such reductions.

Vipul Goyal, Yuval Ishai, Yifan Song