On lower bounds for garbling schemes

Secure 2-party computation allows 2 parties to compute a function on their secret inputs. For example, two severs might hold a share k1 and k2 of a secret-key and compute the encryption enc(k1 xor k2,m) of message m.

A garbling scheme first garbles circuit C, for example enc(k1 xor . , . ) in our example. Then, jointly, both parties garble the input, (k2,m) in our example, and now, server 2 can evaluate the garbled circuit on the garbled input and obtains the result of the function, enc(k1 xor k2,m) in our example.

In this talk, we revisit how efficient the garbling of the input can be when the circuit is garbled first (adaptive security). We explore an existing lower bound security by Applebaum, Ishai, Kushilevitz and Waters (Crypto 2013) and tie it closely to the simulation-based security definition of garbling.

We then propose a weaker simulation-based definition which suffices for our use case, but does not seem to suffer from the same lower bound.