Secure two-party computation via cut-and-choose oblivious transfer

Secure two-party computation via cut-and-choose oblivious transfer

Yehuda Lindell, Benny Pinkas
J Cryptology 2012 [pdf] [bibtex]

Presents several efficiency improvements to the cut-and-choose mechanism for malicious-secure Yao's protocol.

Input consistency

To ensure consistency of the sender's inputs, input wire labels are chosen in a particular way. Namely, the sender chooses random secrets ⚠ {$\{a_i^0, a_i^1, r_j\}$} and sets the wire labels for the ⚠ {$i$}th wire in the ⚠ {$j$}th circuit to be ⚠ {$g^{a_i^0 \cdot r_j}, g^{a_i^1 \cdot r_j}$}, where ⚠ {$g$} is the generator of a cyclic group where DDH holds. Later, the sender can prove consistency of her inputs using a highly efficient zero-knowledge proof for Diffie-Hellman tuples.

Cut-and-choose OT

The authors present a new variant of oblivious transfer called cut-and-choose OT. The main idea is to unify the cut-and-choose circuit checking with the oblivious transfers used to provide the receiver's garbled inputs. In cut-and-choose OT, the sender provides ⚠ {$n$} pairs ⚠ {$(m_0, m_1)$} and the receiver provides a choice bit for each one, as usual. In addition, the receiver provides a subset of ⚠ {$n/2$} indices for which he learns both messages. The sender learns nothing about the receiver's choice bits or the indices for which he learned both sender inputs.

Cut-and-choose OT is used in the 2PC protocol to allow the receiver to pick up his garbled input for evaluation circuits and simultaneously pick up enough information to open the check circuits.

The authors give an efficient construction, again based on the DDH assumption. The starting point is the OT protocol of Peikert, Vaikuntanathan, and Waters. In the PVW protocol, the simulator can extract both sender inputs if a common reference string is a DH tuple. Hence, the idea is to run many copies of the PVW protocol, where the receiver chooses the common reference strings and proves in zero-knowledge that at most half of them are DH tuples.

Performance

The new techniques reduce the number of public-key operations from ⚠ {$O(s^2)$} in previous works LP07 to ⚠ {$O(s)$}, with a small constant. In addition, the cut-and-choose mechanism provides security ⚠ {$2^{-0.311s}$} using ⚠ {$s$} circuits, an improvement over ⚠ {$2^{-s/17}$} in previous work.

Note:

Earlier version published in TCC 2011.

Categories:

CutAndChoose