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.

  1. {$\pi(K) \oplus K \oplus M$}, where {$K = A \oplus B \oplus T$}.
  2. {$\pi(K) \oplus K \oplus M$}, where {$K = 2A \oplus 4B \oplus T$}.
  3. {$\pi(K \| T) \oplus K \oplus M$}, where {$K = A \oplus B$}.
  4. {$\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.