- Computer verification of SMPC protocols by any means necessary
- OWL: Compositional Verification of Security Protocols via an Information-Flow Type System; 2023
- Fuzzy Message Detection; 2021
- PL Theory for SMPC Implementations
- Metadata-privacy preserving Instant Messaging
- Experiment Selection for Causal Discovery; 2013
- Casual security suggestions for friends
- Field Study of Smartphone (Un) Locking Behavior and Risk Perception
- Vuvuzela: Scalable Private Messaging Resistant to Traffic Analysis
- Iconography for key-fingerprint comparison

author | David Heath and Vladimir Kolesnikov |

title | Stacked Garbling: Garbled Circuit Proportional to Longest Execution Path |

howpublished | Cryptology ePrint Archive, Report 2020/973 |

year | 2020 |

where | Georgia Institute of Technology, Atlanta, GA, USA |

This paper outlines a strategy for reducing the size of the object that needs to be communicated from an if-else style branch in a Yao’s Garbled Circuit. The extra size-complexity from the two branch paths (only one of which will actually matter at run-time) is traded for computation-complexity (and some size-complexity that’s O(n) w/r/to the number of inputs to the two branch paths; the authors assume this is small).

Remember that in the context of a boolean circuit we have to use “branchless style” programming.
This usually means that an `if B then X else Y`

gets expressed as `B*X + (!B)*Y`

.
Side effects aren’t really an issue here, but the cost of computing both `X`

and `Y`

when one only needs one of them is unfortunate.

The idea of “stacked garbled circuits” already existed somewhat. It proposes saving the *size* (not the runtime *work*) of the duplicate branches like so:

- Generate each of the two branch circuits deterministically from random seeds.
- XOR them together.
- When the Evaluator needs to evaluate one of the branches, the seed for the
*other*branch is revealed to them (by whatever mechanism). - The Evaluator can now generate (from the seed) the entirety of the branch they
*won’t*be taking. They can learn as much as they want about this branch, because it’s a dead-end that doesn’t affect the rest of the circuit. - Using XOR, the Evaluator can then retrieve the proper version of the
*target*branch (but not any artifacts from during its generation). - The evaluator evaluates the target branch as normal.

Step 3 above is the hard part. Prior works have addressed the case where one party or the other knows `B`

, or where mid-computation communication is acceptable. This paper avoids those more specialized cases.

Roughly speaking, the new approach is as follows:

- Use the two possible ciphertext wire-labels for
`B`

as the seeds for the encrypting the*opposite*branch circuits, and XOR the two together. - The inputs and outputs to these two sub-circuits are not their normal nominal wires; extra machinery shims in-between the branches and the rest of the circuit:
- The “Demux” is basically a small conditional block, switching on
`B`

, on each input wire, such that each branch,*iff*it’s the target branch, gets wire-labels that*do*represent the its input values. If it’s*not*the target branch, then the Demux gives it labels representing whatever values (zeros) the Generator likes, so that the Generator can know in advance what result the Evaluator will get when they evaluate the non-target branch. - The “Mux” takes the two sets of “output” values from the two branches, and returns the one that’s
*not*the nonsense predetermined by the Demux.

- The “Demux” is basically a small conditional block, switching on
- When the Evaluator is ready to evaluate the conditional, they’ll have
*a*label for`B`

, but they won’t know which one it is. They make*both*assumptions, that it represents True/1, and subsequently (or in parallel) that it represents False/0. - Under one of the two assumptions, the Evaluator will correctly generate the non-target branch circuit from its seed, retrieve the target branch via XOR, and evaluate it to get it’s output. Under the other assumption, everything they produce will be meaningless gibberish,
*but the evaluator won’t be able to tell the difference!* - The Evaluator passes the two outputs to the Mux. Whichever of them is gibberish will be gibberish that was known to the Generator in advance; the Mux will be able to filter it out and pass (a new representation of) the correct output to the rest of the circuit. Since both the Mux and Demux are themselves garbled Circuits, they’re opaque to the Evaluator; the Evaluator never learns which of the two branches’ outputs was the correct one.

Thoughts:

- “Mux” is short for “multiplex”; the noun form is “multiplexer”, or “muxer”. It’s really hard to just write “the Mux does
*x*”, but that’s what the authors call it. - This can all be extended to branches with more than two paths.
- They’re explicitly relying on a Random Oracle assumption, but they mention that it might not actually be necessary.
- Is there any possibility of cutting out the extra computation cost?