Irving Street Functionality

This is supposed to be a blog.
recent posts
posted 19 Jan, 2021

Stacked Garbling; David Heath and Vladimir Kolesnikov; 2020

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:

  1. Generate each of the two branch circuits deterministically from random seeds.
  2. XOR them together.
  3. When the Evaluator needs to evaluate one of the branches, the seed for the other branch is revealed to them (by whatever mechanism).
  4. 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.
  5. Using XOR, the Evaluator can then retrieve the proper version of the target branch (but not any artifacts from during its generation).
  6. 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:

  1. Use the two possible ciphertext wire-labels for B as the seeds for the encrypting the opposite branch circuits, and XOR the two together.
  2. 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.
  3. 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.
  4. 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!
  5. 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: