2007 | OriginalPaper | Chapter
Efficient Two-Party Secure Computation on Committed Inputs
Authors : Stanisław Jarecki, Vitaly Shmatikov
Published in: Advances in Cryptology - EUROCRYPT 2007
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.