Foundations of Garbled Circuits

Foundations of Garbled Circuits

Mihir Bellare, Viet Tung Hoang, Phillip Rogaway
ACM CCS 2012 [pdf] [bibtex]

Defines a cryptographic primitive called a "garbling scheme", providing a clean abstraction of many results that use the garbled circuits technique. Most results that use garbled circuits can instead be based on any garbling scheme with a particular security property.

A garbling scheme consists of the following algorithms (stated in terms of circuits, although the abstraction supports garbling other models of computation):

  • ⚠ {$\mathsf{Gb}$}: takes a circuit ⚠ {$f$} and generates a garbled circuit ⚠ {$F$}, encoding table ⚠ {$e$}, and decododing table ⚠ {$d$}.
  • ⚠ {$\mathsf{En}$}: takes encoding table ⚠ {$e$}, input ⚠ {$x$}, and returns a garbled input ⚠ {$X$}
  • ⚠ {$\mathsf{Ev}$}: takes a garbled circuit ⚠ {$F$}, garbled input ⚠ {$X$}, and returns a garbled output ⚠ {$Y$}
  • ⚠ {$\mathsf{De}$}: takes a decoding table ⚠ {$d$}, garbled output ⚠ {$Y$}, and returns a (plaintext) output ⚠ {$y$}

Several properties of garbling schemes are defined:

  • Correctness: If ⚠ {$(F,X,d) \gets \mathsf{Gb}(f)$} then ⚠ {$\mathsf{De}( d, \mathsf{Ev}(F, \mathsf{En}(e, x))) = f(x)$} for all ⚠ {$x$}.
  • Privacy: ⚠ {$(F,X,d)$} should contain no more information than ⚠ {$x$}, ⚠ {$f(x)$}, and the prescribed leakage function of ⚠ {$f$}. Examples of leakage functions include: the entire circuit, the circuit topology only, the number of input/output/internal gates only. Natural indistinguishability and simulation-based definitions are given.
  • Obliviousness: ⚠ {$(F,X)$} alone (i.e., without the decoding table) should contain no information about the output ⚠ {$f(x)$}. Again, indistinguishability and simulation-based variants are defined.
  • Authenticity: Given ⚠ {$(F,X)$} alone, it should be hard to compute ⚠ {$Y'$} such that ⚠ {$\mathsf{De}(d,Y') \not\in \{ f(x), \bot\}$}.
  • Projectivity: Not a security property, but a syntactic one. The encoding table is ⚠ {$e = (X_1^0, X_1^1, \ldots, X_n^0, X_n^1)$}, and ⚠ {$\mathsf{En}(e,x) = (X_1^{x_1}, \ldots, X_n^{x_n})$}. Projective schemes are most common in practical instantations, so that the garbled input can be obtained through an oblivious transfer.

Many previous works are recast in terms of garbling schemes, and their requirements for the above properties are identified.

Two garbling schemes are presented, where the gate-level cipher is abstracted as a primitive called a dual-key cipher. Some instantiations of dual ciphers are given:

  • ⚠ {$E(K_0,K_1,M,T) = F(K_0,T) \oplus F(K_1,T) \oplus M$}, where ⚠ {$F$} is a PRF.
  • ⚠ {$E(K_0,K_1,M) = F(K_0,F(K_1,M))$}, when ⚠ {$F$} is an ideal cipher.
  • ⚠ {$E(K_0,K_1,M,T) = AES(const,K) \oplus K \oplus M$}, where ⚠ {$K = K_0 \oplus K_1 \oplus T$}, modelling fixed-key AES as a random permutation (with the adversary having access to the permutation and its inverse).

These dual-key cipher instantiations also discussed further in (BHKR13).

See also:

BHKR13

Categories:

Garbling