MMap + Leveled FHE ⇒ iO

Standard model · heuristic candidate · GGHRSW13

Statement

GGHRSW13 give the first candidate iO for all polynomial-size circuits: an ${\mathrm{NC}}^1$ obfuscator from candidate multilinear maps (graded encodings), bootstrapped to all circuits with leveled fully homomorphic encryption. They give no reduction from a standard-model multilinear-map assumption.

Sketch

The ${\mathrm{NC}}^1$ obfuscator turns a circuit into a matrix branching program via Barrington’s theorem, rerandomizes it Kilian-style, and publishes the matrices under a graded encoding; evaluation multiplies the input-selected encodings and zero-tests the product. Obfuscating the ${\mathrm{NC}}^1$ circuit that checks a low-depth proof of correct homomorphic evaluation and then decrypts bootstraps the construction to all polynomial-size circuits.

Notes

• A simplified branching-program obfuscator for ${\mathrm{NC}}^1$ is virtual-black-box secure, hence iO-secure, in a generic multilinear-map model — BGKPS14.
• The underlying multilinear-map candidates have since been attacked: CLT13 — CHLRS15; GGH13 as used in obfuscation — MSZ16.