Reusing input labels in half-gate construction

sinu

10/16/23, 7:41 PM

In the half-gate construction of garbled circuits, is it possible to garble multiple instances of a circuit while re-using certain input labels?

Suppose Alice and Bob would like to compute a function using garbled circuits. Alice will act as the generator and Bob the evaluator.

As usual, Alice generates the input labels for the circuit $W_A$ for her inputs, and $W_B$ for Bob's then sends the encrypted gates and her active labels $w_A$. Bob retrieves his active input labels $w_B$ using oblivious transfer and evaluates the circuit.

Now, my question:

Is it secure for Alice to generate a new garbled circuit, where her input labels $W_A$ are new labels but she reuses Bob's existing labels $W_B$ from the previous GC? Such that Bob does not need to retrieve his active labels using OT again (his input is constant), and Alice is assured that Bob's input for this next evaluation is the same as the previous evaluation.

0 + 2

garbled-circuits

lamba

10/17/23, 7:49 AM

The way I think about it is your two circuits can be essentially a single circuit, i.e., your two circuits are connected by $W_B$. Then the property you want is "streaming" where Alice garbles but Bob's allowed to evaluate as soon as some gates are done garbling, he doesn't need to wait for all gates to be done, which should be possible if your garbling scheme supports it. Streaming should be a generalization of what you want to achieve.

sinu

10/17/23, 4:16 PM

Ah right, framing it that way makes sense. In our context it helps to model them as different executions, but you're right in the general sense it seems indistinguishable from streaming. Thank you

Elon Musk

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

EN: Reusing input labels in half-gate construction

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.