Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) iacr.org. You can also receive updates via:
To receive your credentials via mail again, please click here.
You can also access the full news archive.
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.
defined by trinomials. For these two fields, we show that our proposal outperforms the previous best known results if the space and time complexities are both considered.
With this approach we prove our protocol universally composable-secure against a malicious adversary assuming access to oblivious transfer, commitment and coin-tossing functionalities in the random oracle model.
Finally, we construct, and benchmark, a SIMD implementation of this protocol using a GPU as a massive SIMD device. The findings compare favorably with all previous implementations of maliciously secure, two-party computation.