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.