Witness encryption

Witness encryption for an $\mathbf{NP}$ relation $\mathcal{R}$ encrypts a message under a statement $x$, so that anyone holding a witness $w$ with $(x,w)\in \mathcal{R}$ can decrypt, while for a false statement the ciphertext hides the message — GGSW13.

Syntax

A witness encryption scheme for an $\mathbf{NP}$ relation $\mathcal{R}$ with language $L$ is a pair of efficient algorithms $(\mathsf{Enc},\mathsf{Dec})$:

• $\mathsf{Enc}(1^{\lambda },x,m)\to c$, a randomized algorithm taking a statement $x$ and a message $m\in \{0,1\}$,
• $\mathsf{Dec}(c,w)\to m$ or $\perp$, a deterministic algorithm taking a ciphertext and a candidate witness.

Witness encryption without further qualification means a scheme for an $\mathbf{NP}$-complete relation, such as Exact Cover in GGSW13, and hence, composed with a Levin reduction (a Karp reduction together with an efficient map from witnesses of $x$ to witnesses of its image), for every $\mathbf{NP}$ relation — standard. For a language in $\mathbf{P}$ the notion is trivial: encrypt $m$ in the clear when $x\in L$ and a fixed string otherwise.

Properties

Correctness

For all $\lambda$, all $(x,w)\in \mathcal{R}$ and all $m\in \{0,1\}$, $\mathrm{Pr}\left[\mathsf{Dec}(\mathsf{Enc}(1^{\lambda },x,m),w)=m\right]\ge 1-\mathrm{negl}(\lambda )$ over the coins of $\mathsf{Enc}$.

Soundness security

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{we}}_{\calA}(\secpar, x)$}
\begin{algorithmic}
\Comment{The statement $x \notin L$ is fixed in advance}
\State $b \getsr \bits$
\State $c \gets \Enc(1^\secpar, x, b)$
\State $b' \gets \calA(1^\secpar, x, c)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

A witness encryption scheme is sound-secure if for all efficient $\mathcal{A}$ and every sequence $(x_{\lambda }{)}_{\lambda \in \mathbb{N}}$ with $x_{\lambda }\notin L$ and $|x_{\lambda }|\le \mathrm{poly}(\lambda )$,

$${\mathbf{Adv}}_{\mathcal{A}}^{\mathrm{we}}(\lambda ,x):=\left|2\mathrm{Pr}\left[{\mathbf{G}}_{\mathcal{A}}^{\mathrm{we}}(\lambda ,x)=1\right]-1\right|$$

is negligible — GGSW13. The challenger cannot in general decide whether $x\notin L$, so $x$ is fixed by the quantifier rather than chosen by $\mathcal{A}$.

Variations

Extractable witness encryption

A stronger notion requires, for every statement $x$, that any efficient adversary distinguishing encryptions of $0$ and $1$ under $x$ with non-negligible advantage yields an efficient extractor that outputs a witness for $x$ with non-negligible probability — GKPVZ13. With auxiliary input, extractable witness encryption conflicts with plausible special-purpose obfuscation — GGHW14.

Other results

• Combined with standard primitives, witness encryption gives PKE, IBE and attribute-based encryption — GGSW13.

Participates in

Builds on Witness encryption

• WE + PRG ⇒ PKE (GGSW)

Produces Witness encryption

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