International Association
for Cryptologic Research

Witness encryption (WE) is an exciting new primitive introduced by Garg et al. (STOC 2013). WE is defined for some NP language $L$ and allows to encrypt a message relative to an instance $x$ so that one can decrypt with any $w$ witnessing $x \\in L$. Garg et al. construct WE for one NP-complete language from multilinear maps and give another construction from indistinguishability obfuscation (FOCS 2013). Due to the reliance on such heavy tools, WE can currently hardly be implemented on powerful hardware and will not be realizable on constrained devices like smart cards any time soon.

In this paper we construct a witness encryption scheme where \\emph{encryption} is a single Naor-Yung encryption (two CPA-encryptions and one NIZK proof showing the ciphertexts encrypt the same message), so encryption can even be done on a smart card. To achieve this, our scheme has a setup phase, which outputs public parameters containing an obfuscated circuit (only required for decryption), two public keys for a standard public-key encryption scheme and a common reference string for the NIZK (used for encryption). This setup phase need only be run once, and the parameters can be used for arbitrary many encryptions. Our scheme can easily be turned into a \\emph{functional} WE scheme, where a message is encrypted w.r.t. a statement and a function $f$, and using a witness $w$ one learns $f(m,w)$.

Our construction and its proof are inspired by those of functional encryption by Garg et al. (FOCS 2013) and to prove (selective) security of our scheme we also assume indistinguishability obfuscation and statistically simulation-sound NIZK. We give a construction of the latter in bilinear groups and combining it with ElGamal encryption, our ciphertexts are of size 1.3 kB at a 128-bit security level.