Efficient Garbling from a Fixed-Key Blockcipher

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

2013 · 307 citations · 19 references

DOIFull text

Open access

Concepts

TL;DR

The authors propose using fixed‑key AES as the optimal approach for highly efficient circuit garbling. They present schemes that use a single AES call per garbled gate, prove security in the random‑permutation model, and implement them in the Just Garble system. Just Garble evaluates moderate‑sized garbled circuits at an amortized cost of 23.2 cycles per gate (7.25 ns), far faster than any prior results.

Abstract

We advocate schemes based on fixed-key AES as the best route to highly efficient circuit-garbling. We provide such schemes making only one AES call per garbled-gate evaluation. On the theoretical side, we justify the security of these methods in the random-permutation model, where parties have access to a public random permutation. On the practical side, we provide the Just Garble system, which implements our schemes. Just Garble evaluates moderate-sized garbled-circuits at an amortized cost of 23.2 cycles per gate (7.25 nsec), far faster than any prior reported results.

References

19