Look into Damgard-Ishai & Coretti et al. for constant round MPC

Let's look into methods for generating garbled circuits from within MPC. This would lead to a way of doing constant-round computations. Generating the circuit itself just becomes a preprocessing computation.

This Damgard-Ishai paper gives a protocol that looks amenable to our setting: [1] https://iacr.org/archive/crypto2005/36210372/36210372.pdf Coretti et al. also give a closely related protocol that is UC secure: [2] https://eprint.iacr.org/2016/208

Generating a garbled circuit involves going gate by gate through the circuit. For each wire generate random wire labels. Use the combinations of input wire labels as keys, to encrypt the corresponding output wire labels. So, the process roughly consists of 4 encryptions per binary gate. In principle we could run any encryption function as an MPC operation, but this would be presumably be very slow.

Instead, this Damgard-Ishai protocol suggests an approach for encryption that's pretty simple, and the "black box use of PRG" refers to the fact it doesn't involve any complicated functions within the MPC itself. The interface is roughly:

       m <-- Dec( k, C )

in other words it takes as input a secret shared key, and as input a secret shared message. The output is a (public) ciphertext. The idea of the scheme is just to rely on error correcting codes. The key [k] is simply a random secret shared element. The input message [m] is also secret shared. The encryption operation is just that each party applies the prg using their seed to their share of the message, and outputs it. So C = G([k](1)) + [m](1), G([k](2)) + [m](2), ..., G([k](N)) + [m](N). By omitting or reporting incorrect data, the adversary can change the ciphertext. But, given k, since [m] is secret shared, we should be able to reconstruct from the remaining good points anyway. That's a rough explanation of the main idea as I understand it.

Some questions:

Flesh this out and implement it.
It looks like this is going to be O(N^2) or worse, is there a way to amortize it?
Not sure the resilience works out the way we'd want in the async setting. We may have to proceed after only having N-f shares of the ciphertext C. Of these only N-2f may be honest. So we'd need 2f+1 of those to robustly decode. So is this f < n/4 in our setting only? Maybe not - maybe we can proceed with only N-2f and if at some point decoding immediately fails, we then block waiting for the remaining portions of C. Maybe that's OK

initc3 / HoneyBadgerMPC

Look into Damgard-Ishai & Coretti et al. for constant round MPC #178