iO ⇒ Witness encryption

Fully-black-box reduction · standard model · GGHRSW13 · security loss: none: the reduction forwards the adversary’s guess

Statement

iO yields witness encryption for every $\mathbf{NP}$ relation $\mathcal{R}$: $\mathsf{Enc}(1^{\lambda },x,m)$ outputs an obfuscation of the circuit $C_{x,m}(w):=m$ if $(x,w)\in \mathcal{R}$ and $\perp$ otherwise, and $\mathsf{Dec}(c,w)$ runs the obfuscated circuit on $w$ — GGHRSW13.

Sketch

For $x\notin L$, both $C_{x,0}$ and $C_{x,1}$ output $\perp$ on every input, so they are functionally equivalent circuits of the same size, and iO makes their obfuscations indistinguishable.

Notes

• The first witness encryption scheme is built directly from multilinear maps: MMap ⇒ WE — GGSW13.