A method for reducing the size of a garbled truth table in constructions of garbled circuits. The basic concept was first introduced by Philip Rogaway. Consider the "first" ciphertext `⚠️{$\mathsf{Enc}_{A,B}(C)$}`

of a garbled gate, where `⚠️{$A,B$}`

are wire labels of input wires and `⚠️{$C$}`

is a wire label of the output wire. In a "textbook" garbled circuit, `⚠️{$C$}`

is chosen randomly. Garbled row reduction suggests to choose `⚠️{$C$}`

indirectly as the value that causes `⚠️{$\mathsf{Enc}_{A,B}(C) = 0^k$}`

(this can be made possible when using the point and permute optimization, where the `⚠️{$\mathsf{Enc}$}`

can be a simple cipher rather than a full-fledge encryption scheme). As such, the first ciphertext does not need to be sent (it will always be the all-zeroes string), reducing the size of the garbled gate by 25%. A more sophisticated technique that reduces the size by 50% was described in PSSW09.

- Home page
- All papers, by:
- .. category
- .. author names
- .. publication date
- .. recently added
- .. recently updated

- Glossary
- About
- Just getting started in MPC?
- Guidelines
- Todo List

Search Papers

Bibliography Categories