Join Log in
Score:1
walter7x avatar Crypto

How to securely set constant values inside garbled circuits?

tr flag
walter7x

Suppose there are some constant values which must be set inside the circuit. The naive way is to simply pass the needed constants as inputs to the circuit. But this seems wasteful.

What it the proper way of setting (i.e. hard-coding) constant values in the garbled circuits?

85
0 + 0
Score:0
avatar Crypto
us flag
Mikero

I'll assume that these hard-coded constants are public (known to both garbler and evaluator). There are a few options:

  1. Treat the constants as extra inputs to the circuit, like you suggest. Note that input wires can be reused for many gates, so you only need a single true and false wire for the entire circuit. Most garbling schemes support not gates for free, so you actually only need a constant true wire. Furthermore, it turns out that you can always take the true wire label to be the string of all zeroes, without loss of generality. Combining all of these observations, the extra constant input wires add no cost to the circuit.

  2. Propagate constants through the circuit. For example, a gate y=AND(x,true) becomes just y=x, meaning that you can replace the y wire by x in any downstream gates that use y as an input. A gate y=AND(x,false) becomes y=false, and you can again propagate y=false downstream in gates that use y as an input. By doing this, you'll see that many gates downstream of the hard-coded constant can simply be removed entirely from the circuit. This process has nothing to do with garbling, but is just simplifying the boolean circuit based on hard-coded inputs.

If the constants are known only to the garbler, then the goal is to simplify the circuit/garbling while hiding those constants.

Most garbling schemes (and certainly the leading state of the art ones) support gates that absorb free not gates, meaning that you can garble and(not(x),y), and(x,not(y)), ... gates for the same cost as garbling an and gate. In fact, these garbling schemes hide the existence of these not gates. Using this observation, you can still do #1 from above. If you need to hard code a gate y=and(x,false) then you can feed your single true input wire into a gate of the form y=and(x,NOT(true)) while hiding the presence of that not (i.e., hiding whether the gate was hard-coded with a true or false).

However, you can do slightly better by using the "garbler half-gate" from the half-gates construction. This lets you garble an and(x,true) or and(x,false) gate, while hiding which one is garbled, for half the cost of a full-fledged and-gate.

0 + 0
walter7x avatar
tr flag
walter7x
Thank you @Mikero, in my case I use BHKR13 (fixed-key AES) + FreeXOR + GRR3. The constants are public. Option 1 (inputting one true wire and one false wire) is the most attractive, however I'm worried that if e.g. two 0 bits of the constant need to be XORed with each other inside the circuit, this means XORing the same wire with itself which will result in label0 = 0 and label1 = circuit's delta. Do I have to make sure that the circuit is arranged so that label1 will not end up being an output label of the circuit? Or did I miss your idea entirely?
0
Reply
us flag
Mikero
It is true that a gate `y xor y` gives false, including the case where y is hard-coded. With free-xor, this gate's output wires are indeed 0 and $\Delta$. Since it is impossible for this gate to give output=true, the usual security tells you that it is impossible for the evaluator to learn the true wire label $\Delta$. When you think about it, the evaluator is just xor'ing a wire label by itself, which she could do even if there is no such xor gate in the circuit -- so if these kinds of gates leaked $\Delta$ then an evaluator could break any circuit by simply imagining such a gate.
0
Reply
walter7x avatar
tr flag
walter7x
So, would it be possible instead of providing one true and one false inputs to the circuit, to 1) take any non-constant input wire, 2) xor it with itself to get wire x =false, 3) set wire y = NOT(x) =true, 4) use wires x and y to set any constant values?
0
Reply
us flag
Mikero
Yes, that would work too, and would be an equivalent way of interpreting the "let the constant `false` input have an all-zeroes wire label" approach.
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.