**Witness Encryption and its Applications**

*Sanjam Garg and Craig Gentry and Amit Sahai and Brent Waters*

**Abstract: **We put forth the concept of \emph{witness encryption}. A witness encryption scheme is defined for an NP language $L$ (with corresponding witness relation $R$). In such a scheme, a user can encrypt a message $M$ to a particular problem instance $x$ to produce a ciphertext. A recipient of a ciphertext is able to decrypt the message if $x$ is in the language and the recipient knows a witness $w$ where $R(x,w)$ holds. However, if $x$ is not in the language, then no polynomial-time attacker can distinguish between encryptions of any two equal length messages. We emphasize that the encrypter himself may have no idea whether $x$ is actually in the language.

Our contributions in this paper are threefold. First, we introduce and formally define witness encryption. Second, we show how to build several cryptographic primitives from witness encryption. Finally, we give a candidate construction based on the NP-complete \textsc{Exact Cover} problem and Garg, Gentry, and Halevi's recent construction of ``approximate" multilinear maps.

Our method for witness encryption also yields the first candidate construction for an open problem posed by Rudich in 1989: constructing computational secret sharing schemes for an NP-complete access structure.

**Category / Keywords: **public-key cryptography / Multilinear Maps

**Date: **received 6 May 2013, last revised 17 Apr 2014

**Contact author: **sanjamg at cs ucla edu

**Available format(s): **PDF | BibTeX Citation

**Version: **20140418:025904 (All versions of this report)

**Short URL: **ia.cr/2013/258

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]