Efficient Two-Party Secure Computation on Committed Inputs

We present an efficient construction of Yao’s “garbled circuits” protocol for securely computing any two-party circuit on committed inputs. The protocol is secure in a universally composable way in the presence of

malicious

adversaries under the decisional composite residuosity (DCR) and strong RSA assumptions, in the common reference string model. The protocol requires a constant number of rounds (four-five in the standard model, two-three in the random oracle model, depending on whether both parties receive the output),

O

(|

C

|) modular exponentiations per player, and a bandwidth of

O

(|

C

|) group elements, where |

C

| is the size of the computed circuit.

Our technical tools are of independent interest. We propose a homomorphic, semantically secure variant of the Camenisch-Shoup verifiable cryptosystem, which uses shorter keys, is

unambiguous

(it is infeasible to generate two keys which successfully decrypt the same ciphertext), and allows efficient proofs that a committed plaintext is encrypted under a

committed key

.

Our second tool is a practical four-round (two-round in ROM) protocol for

committed

oblivious transfer on

strings

(string-COT) secure against malicious participants. The string-COT protocol takes a few exponentiations per player, and is UC-secure under the DCR assumption in the common reference string model. Previous protocols of comparable efficiency achieved either committed OT on

bits

, or standard (non-committed) OT on strings.