Paper 2014/273

Witness Encryption from Instance Independent Assumptions

Craig Gentry, Allison Bishop Lewko, and Brent Waters


Witness encryption was proposed by Garg, Gentry, Sahai, and Waters as a means to encrypt to an instance, x, of an NP language and produce a ciphertext. In such a system, any decryptor that knows of a witness w that x is in the language can decrypt the ciphertext and learn the message. In addition to proposing the concept, their work provided a candidate for a witness encryption scheme built using multilinear encodings. However, one significant limitation of the work is that the candidate had no proof of security (other than essentially assuming the scheme secure). In this work we provide a proof framework for proving witness encryption schemes secure under instance independent assumptions. At the highest level we introduce the abstraction of positional witness encryption which allows a proof reduction of a witness encryption scheme via a sequence of 2^n hybrid experiments where n is the witness length of the NP-statement. Each hybrid step proceeds by looking at a single witness candidate and using the fact that it does not satisfy the NP-relation to move the proof forward. We show that this isolation strategy enables one to create a witness encryption system that is provably secure from assumptions that are (maximally) independent of any particular encryption instance. We demonstrate the viability of our approach by implementing this strategy using level n-linear encodings where n is the witness length. Our complexity assumption has approximately n group elements, but does not otherwise depend on the NP-instance x.

Available format(s)
Publication info
Preprint. MINOR revision.
Witness Encryption
Contact author(s)
bwaters @ cs utexas edu
2014-04-30: last of 2 revisions
2014-04-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Craig Gentry and Allison Bishop Lewko and Brent Waters},
      title = {Witness Encryption from Instance Independent Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2014/273},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.