We construct a WE scheme where \emph{encryption} is done by simply computing a Naor-Yung ciphertext (two CPA encryptions and a NIZK proof). To achieve this, our scheme has a setup phase, which outputs public parameters containing an obfuscated circuit (only required for decryption), two encryption keys and a common reference string (used for encryption). This setup need only be run once, and the parameters can be used for arbitrary many encryptions. Our scheme can also be turned into a \emph{functional} WE scheme, where a message is encrypted w.r.t. a statement and a function $f$, and decryption with a witness $w$ yields $f(m,w)$.
Our construction is inspired by the functional encryption scheme by Garg et al. and we prove (selective) security assuming iO 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 and can be computed on a smart card.
Category / Keywords: Witness Encryption, Indistinguishability Obfuscation, NIZK, Groth-Sahai proofs. Date: received 30 Aug 2015, last revised 6 Oct 2015 Contact author: habusalah at ist ac at Available format(s): PDF | BibTeX Citation Note: Revised related-work section, and strengthened definition/construction of offline FWE. Version: 20151006:194414 (All versions of this report) Short URL: ia.cr/2015/838 Discussion forum: Show discussion | Start new discussion