Join Log in
Score:3
walter7x avatar Crypto

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

tr flag
walter7x

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.

112
1 + 0
Score:2
Geoffroy Couteau avatar Crypto
cn flag
Geoffroy Couteau

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)

0 + 1
us flag
Mikero
This is very sensitive to subtle details about how garbled circuits are used in the protocol. In Dupin-Pointcheval-Bidan, it is important that there are commitments on the output wires. Without those commitments, it is easy for the *garbled* output (not the "decoded" output) to leak the evaluator's entire input. We have a [paper](https://eprint.iacr.org/2015/055.pdf) that explores how the evaluator can be sure that a garbled circuit computes according to the expected circuit topology. As in DPB, the issue is wires that encode more than 2 values.
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.