iO + OWF ⇒ Multiparty NIKE (Boneh–Zhandry)

Free reduction · standard model · BZ14 · security loss: polynomial

Statement

If iO and one-way functions exist, then for every polynomial $N$ there is an $N$-party non-interactive key exchange without trusted setup, in which each party’s published value has length independent of $N$ — BZ14.

Sketch

Each party publishes $s_i^{\prime }=G(s_i)$ for a length-doubling PRG $G$ and a uniform seed $s_i$. The shared key is a puncturable PRF evaluated at $(s_1^{\prime },\dots ,s_N^{\prime })$, computed through an obfuscated program that releases it only to a caller presenting a seed $s_i$ with $G(s_i)=s_i^{\prime }$ for one of the listed values. Punctured programming, together with replacing each $s_i^{\prime }$ by a uniform string outside the image of $G$, shows the key is pseudorandom to an eavesdropper — BZ14.

Notes

• For $N=2$ Diffie–Hellman already works (DDH ⇒ NIKE) — DH76 — and for $N=3$ a bilinear pairing — Jou04.
• The same paper uses iO to build broadcast encryption with short ciphertexts and traitor tracing with short ciphertexts and keys — BZ14.