Efficient Garbling from a Fixed-Key Blockcipher

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.

Categories:

Garbling