Multilinear No-Exact-Cover ⇒ Witness encryption (GGSW)

Standard model · GGSW13 · security loss: tight: the assumption is the scheme’s security on Exact Cover instances without a cover, and the Karp reduction to Exact Cover preserves it

Statement

From multilinear maps under the Decision Multilinear No-Exact-Cover assumption, which GGSW13 introduce, there is witness encryption for the $\mathbf{NP}$-complete problem Exact Cover, hence for every $\mathbf{NP}$ relation — GGSW13.

Sketch

For an Exact Cover instance over a universe $[n]$ with sets $S_1,\dots ,S_{\ell }$, sample $a_1,\dots ,a_n$ and publish, for each $S_i$, an encoding of ${\prod }_{j\in S_i}{a}_j$ at level $|S_i|$. The message is masked by a key extracted from the level-$n$ encoding of ${\prod }_{j\in [n]}{a}_j$. An exact cover multiplies the published encodings to exactly that encoding, and the Decision Multilinear No-Exact-Cover assumption says the key is pseudorandom when no exact cover exists — GGSW13.

Notes

• Witness encryption with a pseudorandom generator gives PKE: WE + PRG ⇒ PKE — GGSW13.