Paper 2016/1032

Efficient Covert Two-Party Computation

Stanislaw Jarecki

Abstract

Covert computation of general functions strengthens the notion of secure computation, so that the computation hides not only everything about the participants' inputs except for what is revealed by the function output, but it also hides the very fact that the computation is taking place, by ensuring that protocol participants are indistinguishable from random beacons, except when the function output explicitly reveals the fact that a computation took place. General covert computation protocols proposed before have non-constant round complexity [16,4] and their efficiency is orders of magnitude away from known non-covert secure computation protocols. Furthermore, [8] showed that constant-round covert computation of non-trivial functionalities with black-box simulation is impossible in the plain model. However, the lower-bound of [8] does not disallow constant-round covert computation given some relaxation in the computation model. Indeed, in this work we propose the first constant-round protocol for covert Two-Party Computation (2PC) of general functions, secure against malicious adversaries under concurrent composition, assuming the Common Reference String (CRS) model. Our protocol is a covert variant of a well-known paradigm in standard, i.e. non-covert, secure 2PC, using cut-and-choose technique over O(security parameter) copies of Yao's garbled circuit protocol, and its efficiency is only a constant factor away from non-covert secure 2PC protocols that use cut-and-choose over garbled circuits. An essential tool in the protocol is a concurrently secure covert simulation-sound Conditional KEM (CKEM) for arithmetic languages in prime-order groups. We show that the Implicit Zero-Knowledge arguments in the CRS model of Benhamouda et al. [2] provide covert CKEM's for all languages needed in our covert 2PC protocol. We also show that in the Random Oracle Model the covert CKEM's of [11] also satisfy concurrent security and simulation-soundness. The ROM-based covert CKEM's of [11] match the cost of ROM-based NIZK's for the same languages, while the CRS-model CKEM's of [2] are (only) 2-4 times more expensive.