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