## Efficient Garbling from a Fixed-Key Blockcipher

*Mihir Bellare, Viet Tung Hoang, Sriram Keelveedhi, Phillip Rogaway*

SSP 2013 [pdf] [bibtex]

This paper proposes to take advantage of very fast hardware AES-NI instructions in the design of circuit garbling schemes. The fastest way to exploit AES instructions is to fix a *publicly known* AES key {$k$} for the duration of garbling, and repeatedly make calls to the induced permutation {$AES_k(\cdot)$}.

Note that under this setting, an adversary would also have access to the inverse permutation {$AES_k^{-1}(\cdot)$}. The challenge in this work is, therefore, how to design secure garbling schemes under the assumption that all parties have oracle access to a randomly chosen block permutation {$\pi$} and its inverse {$\pi^{-1}$}.

Specifically, the authors propose the following candidates for gate-level ciphers {$E(A,B,M,T)$}, where {$A,B$} are the two incoming wire labels, {$M$} is the outgoing wire label, and {$T$} is a tweak.

- {$\pi(K) \oplus K \oplus M$}, where {$K = A \oplus B \oplus T$}.
- {$\pi(K) \oplus K \oplus M$}, where {$K = 2A \oplus 4B \oplus T$}.
- {$\pi(K \| T) \oplus K \oplus M$}, where {$K = A \oplus B$}.
- {$\pi(K \| T) \oplus K \oplus M$}, where {$K = 2A \oplus 4B$}.

In all of the above ciphers, {$2A$} denotes a doubling in a finite-field, or other simple low-level operation.

All schemes are proven secure ciphers for a standard garbling approach. Schemes 2 and 4 are proven secure for the free XOR optimization as well as the simple (4-to-3) row reduction optimization.

### Categories:

- 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