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.