## 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