Cheaper bit-by-bit inputs for garbled computation over large prime fields

What is it about?

Garbling schemes let two parties who do not trust each other compute a function together. One party, the garbler, prepares an encrypted version of the computation that hides his secret input. The other party, the evaluator, runs it on her own input and learns only the result. The classic scheme of Yao handles the evaluator's input one bit at a time. This is what makes it easy to combine with other tools, such as oblivious transfer or one-time signatures. Newer schemes work directly with large numbers and are much more efficient, but they take the evaluator's input as a whole number, so they no longer fit those tools. The standard fix is to split each number into its bits and pay for every bit, which makes the encoding hundreds of times larger. We give a translation from bit-by-bit inputs to large-number inputs whose cost is about the same as the size of inputs and outputs themselves.

Featured Image

Photo by Brad Switzer on Unsplash

Photo by Brad Switzer on Unsplash

Why is it important?

Bitcoin bridges are where this matters most right now. Recent designs for trust-minimized Bitcoin bridges use garbled circuits to check proofs off-chain. Their inputs have to be revealed bit by bit, because Bitcoin authenticates them with Lamport signatures. Both designs build an efficient garbling scheme over a large field and then split the input into bits, which is where most of their size comes from. Our technique replaces that step directly and improves over prior work by 23-51x. The same technique also gives the best known way to build vector OLE over large fields from plain oblivious transfer and hashing. Vector OLE is a basic building block for arithmetic MPC and zero-knowledge proofs.

Perspectives