How can malicious garbling compromise evaluator's input in Yao's garbled circuit

Question

Suppose, we have a circuit which outputs a sha256 hash of a concatenation of Alice's input and Bob's input (where Alice is the garbler and Bob is the evaluator).

I am trying to understand what methods can Alice resort to when garbling the circuit maliciously to leak at least one bit of Bob's input into the output. (It is not as important in my case that the circuit's output will be wrong, only that Bob's input is not leaked)

Examining the source code of JIGG I see that Bob receives from Alice garbled truth tables for all AND gates in the circuit. He does not need the truth tables for the XOR gates (because of FreeXOR, I assume).

Am I correct in assuming that "rigging" the AND truth table is the only wiggle room for Alice to influence the output. Can it be rigged to always output e.g. 0 regardless of the input wires to the AND gate?

I did read the whole chapter "Malicious Security" of Pragmatic MPC but it does not cover my specific question, only mentions in passing "The output of the maliciously-generated garbled circuit may leak more than P 2 has agreed to reveal (for instance, P 2 ’s entire input)." The book then proceeds to explain how to defend against malicious garbling, it does not explain how exactly the garbler can rig the circuit to leak inputs.

Answer 1

This really depends on which garbling scheme is used. Using the state-of-the-art half-gate scheme (here), your question has been the subject of a paper by Dupin, Pointcheval, and Bidan, which can be found here. The bottom line is: any such attack amounts to adding or removing NOT gates arbitrarily in the original circuit. Whether this can be used to leak the input in full depends on the exact circuit used to implement the hash function (and finding out the exact answer can be quite tricky, since this boolean circuit can be complex).

(As the paper shows, there exists some circuits for which these attacks are provably not an issue, but it seems unlikely to be the case for standard hash functions)