Eurocrypt 2016: All Complete Functionalities are Reversible

In the multi-party computation (MPC) track at Eurocrypt 2016 in Vienna, Austria, Dakshita Khurana rather heroically gave two consecutive, very well-presented talks, the second of which explaining that All Complete Functionalities are Reversible. This second talk is the focus of this blog post.

In the context of MPC, a functionality is an algorithm which performs some operation using two or more parties' inputs while guaranteeing certain requisite security properties. The functionalities covered by this paper are secure function computations (SFEs), in which the parties want to compute some function on their combined inputs in a secure manner.

In the case of functionalities with two parties, $P_A$ and $P_B$, we usually consider one party as the sender and the other as the receiver. For decades, an open question in the field of MPC was, Given a two-party functionality $\mathcal{F}$ in which $P_A$ acts as the sender and $P_B$ as the receiver, is it possible to turn this into a secure scheme in which instead $P_A$ acts as the receiver and $P_B$ as the sender? This reverse functionality is denoted by $\textsf{reverse}(\mathcal{F})$. Intuitively, we think of a functionality allowing this reversal as containing 'enough symmetry' to perform the functionality of $\mathcal{F}$ regardless of which party performs which role.

It was shown by Wolf and Wullschleger that oblivious transfer (OT) can be reversed. OT is a process by which $P_A$ receives one of (at least) two values private to $P_B$ without $P_B$ finding out which $P_A$ chose.

A functionality $\mathcal{F}$ is called complete if both $\mathcal{F}$ and $\textsf{reverse}(\mathcal{F})$ are able to realise OT functionality. In light of Wolf and Wullschleger's result, a natural question to ask is then, Exactly which complete 2PC functionalities can be reversed? This new result shows that they all can be.

The main technical challenge that the authors overcome is that of creating commitments in both directions. This accomplishment is essentially what allows this symmetry property to go through and achieve the result.

As one would hope for in papers on cryptography, this result has practical as well as theoretical appeal: if one party possesses some physical property requiring that it perform a particular role in the functionality (e.g. a computationally 'weak' device), it is essential that this property suffice to compute securely even if roles are reversed. In this way, this paper serves as a good example of how cryptography theory and practice can and should go hand in hand. Like a couple dancing a Viennese waltz?