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.
Category / Keywords: Witness Encryption Date: received 18 Apr 2014, last revised 29 Apr 2014 Contact author: bwaters at cs utexas edu Available format(s): PDF | BibTeX Citation Version: 20140430:050728 (All versions of this report) Short URL: ia.cr/2014/273