A Protocol Issue for the Malicious Case of Garbled Circuit Construction

A Protocol Issue for the Malicious Case of Garbled Circuit Construction

Mehmet Kiraz, Berry Schoenmakers
Information Theory in the Benelux 2006 [pdf]

A subtle security issue is described, regarding cut-and-choose approaches to Yao's protocol. The problem is related to the issue of selective failure attacks. Basically, the parties use oblivious transfer to let the receiver obtain garbled inputs for the evaluation circuits. However, the sender can provide any input to these OTs, and not necessarily the correct wire labels. This leads to concrete violations of security for protocols that preceded this work. Concretely, a secure protocol must somehow link the sender's OT inputs to the values checked in the cut-and-choose phase.

This paper proposes a new variant of OT called committing OT. In this variant, the receiver also receives commitments to both of the sender's inputs (and the sender receives the corresponding openings). Using committing OT in a cut-and-choose protocol, the receiver can pick up his garbled inputs and then later do a cut-and-choose to check some of the circuits. Circuits are checked by opening the committed OT inputs. Intuitively, the cut-and-choose ensures that the unopened commitments --- and hence, the sender's OT inputs --- are valid.

Categories:

CutAndChoose