PRF ⇒ Garbled circuits (BHR)

Fully-black-box reduction · standard model · BHR12

Statement

Any PRF yields a projective garbling scheme achieving privacy: the garbled circuit, together with the input labels of $x$ and the decoding information, can be simulated from $f$ and $f(x)$. The PRF is turned into a dual-key cipher, which encrypts the rows of each gate’s garbled table. BHR12 also analyse the scheme’s concrete security and extend it to obliviousness and authenticity — BHR12.

Notes

• Efficiency: each gate’s garbled table holds four ciphertexts of the dual-key cipher — standard; BHR12 give blockcipher-based instantiations — BHR12.
• With OT, the scheme gives two-party computation secure against semi-honest adversaries (Yao’s protocol) — Yao86, LP09.