Can a garbler "open" a circuit by "opening" only her input labels and AND tables?

walter7x

11/20/22, 2:51 PM

I'm using the word "open" as in chapter 6 "Malicious Security" of Pragmatic MPC, i.e. to "open" the circuit is for the garbler to provide all the randomness used to garble the circuit, so that the evaluator can be sure that the circuit was correctly garbled.

Suppose Bob has just evaluated the circuit which Alice (the garbler) sent to him. But before Bob does anything with the circuit's output, he asks Alice to prove to him that the circuit was garbled correctly.

As I understand, it is paramount for GC security that the evaluator never learns the value of two wire labels going into the same gate.

( Assuming FreeXOR) Alice "opens" all the AND gates' truth tables.
Alice "opens" only those of her input labels which are known to Bob (but keeps her other labels secret).
Alice does not "open" Bob's input lables.

What attacks can Alice mount by not "opening" 1 set of her input labels and all of Bob's input labels? Are there any other subtleties involved in "opening" the circuit that I've overlooked?

0 + 5

multiparty-computation

garbled-circuits

Mikero

11/20/22, 3:57 PM

What exactly do you mean by "opening" an AND gate, if not revealing all 4 input labels to that gate?

walter7x

11/20/22, 4:09 PM

I just look at JIGG's source code and go by that: https://github.com/multiparty/jigg/blob/afb4af1cef0a90cc9272d0daf78bc665100b188f/src/garble.js#L21 There is only one random label in that function, so proving that that random label was randomly generated would constitute "opening" the truth table.

Mikero

11/20/22, 4:17 PM

You propose to reveal one of the 2 output labels. If it's the label that the evaluator already knew, then what does that prove about the correctness of the entire gate (the thing that can go wrong is not this value being chosen non-randomly -- it's that the garbled gate is not computed in the expected way from this value and the input labels)? If it's the label that the evaluator didn't already know, then the evaluator now knows both labels on a single wire, and it sounds like you were trying to avoid that case.

Mikero

11/20/22, 4:18 PM

Also, better garbling schemes (like half-gates) don't have any per-gate randomness. The entire garbled gate + output labels are a deterministic function of the input labels. So there is no extra "seed" to reveal for each gate (even if that somehow worked).

walter7x

11/21/22, 4:34 AM

Thank you for explaining. So, it's not about the value being chosen non-randomly.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Can a garbler "open" a circuit by "opening" only her input labels and AND tables?

TH: คนอ่านไม่ออกสามารถ "เปิด" วงจรโดย "เปิด" เฉพาะป้ายอินพุตและตารางได้หรือไม่

RO: Poate un nenorocit să „deschidă” un circuit „deschizând” doar etichetele de intrare și tabelele SI?

RU: Может ли мошенник «открыть» цепь, «открыв» только ее входные метки и таблицы И?

VI: Người cắt xén có thể "mở" một mạch bằng cách chỉ "mở" nhãn đầu vào và bảng AND của cô ấy không?

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.