Paper 2011/689

(Efficient) Universally Composable Two-Party Computation Using a Minimal Number of Stateless Tokens

Seung Geol Choi, Jonathan Katz, Dominique Schröder, Arkady Yerukhimovich, and Hong-Sheng Zhou

Abstract

We continue the line of work initiated by Katz (Eurocrypt 2007) on using tamper-proof hardware tokens for universally composable secure computation with no additional setup. As our main result, we show an efficient oblivious-transfer (OT) protocol in which two parties each create and exchange a single, stateless token and can then run an unbounded number of OTs. This, in turn, means that the parties can perform (repeated) secure computation of arbitrary functions without exchanging additional tokens. Our protocol yields what we believe is the most practical and efficient known approach for universally composable computation based on tamper-proof hardware. Motivated by our result, we investigate the minimal number of stateless tokens needed for universally composable secure computation. We prove that our protocol is optimal in this regard for constructions having black-box security proofs. We also show that nonblack-box techniques can be used to obtain a construction using only a single stateless token.

Note: There is a security flaw in the protocol from Section 4, as written. The flaw is fixable, and we are currently writing up a version of the paper with a modified protocol and proof.