2
$\begingroup$

Yao Garbled circuit is 2 parties secure computation protocol between Semi honest adversaries. However, the cut-and-choose mechanism complies semi-honest garbled circuits into the one secure against malicious adversaries. Specifically, it provides statistical security against malicious garbler (circuit creator).

My question is as cut-and-choose provides statistical security, can garbler be "unbounded"?

$\endgroup$
2
  • $\begingroup$ Ct2048 welcome to cryptopgraphy S.E. Could you please be more specific about being "unbounded": computatiional, time,... unbounded? $\endgroup$ Apr 15 '20 at 14:42
  • $\begingroup$ By unbounded I mean computationally unbounded $\endgroup$
    – ct2048
    Apr 15 '20 at 14:59
0
$\begingroup$

Cut-and-choose is not a specific protocol that we can analyze, but a general technique whose details can be realized in many ways.

The basic idea of cut-and-choose is to generate many garbled circuits, open some of them to test for correctness, and evaluate the rest. The goal is to ensure that most (or, in some protocols, at least one) circuits used for evaluation are correct. If this condition holds, even of those "correct" circuits were generated by a corrupt garbler, there is no problem. Furthermore, the analysis of how many circuits to generate/open doesn't consider the running time of the corrupt garbler. It is a purely statistical argument. So this central idea of garbled circuits is naturally safe in the presence of an unbounded garbler.

But there are other parts of a "cut-and-choose protocol":

  • The garbler must provide garbled inputs to the receiver, using oblivious transfer (OT). Naturally the OT protocol must be secure against an unbounded sender, and this is possible.

  • The protocol must prevent the garbler from using inconsistent inputs across different garbled circuits. Different protocols vary widely in how they realize these properties. I believe that some are secure against an unbounded garbler, and probably others are not.

  • The protocol must prevent the garbler from causing the receiver to abort with input-dependent probability. Again, whether this is safe against an unbounded garbler depends on how the mechanism is realized. I think that some techniques are safe and others are not.

$\endgroup$
2
  • $\begingroup$ Can you cite the paper that provides security against unbounded garbler? $\endgroup$
    – ct2048
    Apr 16 '20 at 8:44
  • $\begingroup$ "this central idea ... is safe in the presence of an unbounded garbler" --> Only the cut-and-choose step is secure against an unbounded garbler; it doesn't mean that the entire protocol has security against unbounded garbler. $\endgroup$
    – Mikero
    Aug 31 at 4:01
0
$\begingroup$

The cut-and-choose technique is used to prevent a malicious party who can construct garbled circuits incorrectly: because they are encrypted, the receiver can't realize if the sender is cheating. So the cut-and-choose technique works by demanding that the garbler constructs many copies of the required circuit, and open some of them to check.

In order to reach that verification, the garbler commits to his/her inputs, and both parties use oblivious-transfer protocol to realize the cut-and-choose.

So, because commitment and oblivious-transfer are used in this malicious resistant garbled circuit example, the security of this construction depends on the fact that protocols are or are not secure when you consider a computationally unbounded garbler. For example, if the commitment protocol used is not perfect binding... a unbounded grabler can cheat.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.