Obliv-C over encrypted communication?

[weikengchen]

In case the two servers are over the Internet, the communication between them (i.e., OT, Yao's protocol) might need some sort of confidentiality and integrity protection.

Any thoughts about that? One potential idea is to apply Secure Socket API (SSA) (https://owntrust.org/ssa) onto the TCP protocol suite in oblivc_bits.c and add some additional socket flushing.

Yet, think about that Yao's protocol is sending specific data, probably there is a better cryptographic construction for "encrypting/signing the GC".

[samee]

I strongly prefer not to add yet another dependency on the Obliv-C build process, but the suggestion is still interesting. I'd recommend a standalone library that integrates in: you could have your own protocolUseSsa function that initializes the pd->trans object, just like protocolUseTcp2P et al. does. If you write such a library I'd also be happy to point to it from my readme file, for instance.

I don't see a whole lot of value to encrypting anything but the reveal functions, but the integrity properties can still be useful. After all, the whole point of MPC is to not reveal any inputs. Please make sure you note this point in your library, or else users may mistakenly assume GC itself is broken.

To your other point about better constructions, yes, you can probably find a much easier way to sign garbled circuits, albeit less modular. Something like signing feed and reveal logics should probably do the trick, but I didn't think too hard about the proof. And even that would only work for semi-honest protocols. For simple GCs without any interactive inputs, you can probably just sign a hash of the entire protocol transcript from your side and send it off to the other side before a reveal but after end of computation.

[weikengchen]

Thanks for the ideas. Great ideas!

To sum up,

• encryption is only needed for reveal (but not the OT & circuit), as long as the program doesn't do crazy things based on the revealed values;
• authenticating can be done by signing the transcript.

Let me talk a little bit about signing.

I think directly signing the current feed and reveal steps may be insufficient, as follows:

• currently, when we reveal, one party sends only the LSB of the zero-labels of output wires. See https://github.com/samee/obliv-c/blob/obliv-c/src/ext/oblivc/obliv_bits.c#L815 .
• thus, if a malicious party flips some bits of the circuit, it may end up with wrong result, but the two parties are unaware of.

So, some modifications to the current reveal steps will be necessary. However, I think we don't want to send, for example, the hashes of both labels for each wires, which will lead to an 80x blowup for revealing.

[samee]

When you say "malicious party", do you mean some man-in-the-middle, or the party whose signature I am actually expecting? Malicious bit flips by a MITM will always be detected. For the cases where the other legitimate party has turned malicious, yes, you certainly cannot use a semi-honest protocol. A lot of other things need to change for that.

[weikengchen]

I mean man-in-the-middle.

Where is the protection that "Malicious bit flips" will be detected?

[samee]

Take the string of all LSB bits sent during reveal, and sign it. The point of signing is that the other party can verify it with my pre-shared public key.

[weikengchen]

What if the "bit flips" happen in the sending/receiving of garbled gates? I mean, one party already receives incorrect "half-gates".

[samee]

Yes, there are lots of such potential pitfalls, and such a protocol should never be trusted without proper proofs.

[weikengchen]

If we don't just sign the LSB, but sign the hashes of two labels (the 0-label and 1-label), there is still an obstacle:

Maybe a bit flip only makes a gate abnormal IN SOME CASES.

For example, if a gate $g$ was "bit-flipped", maybe the gate still has a correct label for input 1, but a totally incorrect label for input 0.

Thus, there needs a proof showing that "if there is a bit flip, both labels will be affected."

And we need to show that "it is impossible that the affected wire will be later magically corrected in later gates if the attacker makes another bit label."

[weikengchen]

The overkill solution is to sign everything, including OT and the circuit.

So, I smell some academic research here... even in the malicious case, we don't want a network attacker to easily create chaos, right?

[weikengchen]

The motivating example for malicious case (off-topic for Obliv-C):

10 companies are actually honest, but they run a maliciously secure 10-party federated learning platform. After THREE months of computation, they figured out that on the second day, a malicious attacker flipped one bit -- but they were previously unaware of that.

The eventual result, after the three months, becomes totally useless.