Practical Witness Encryption for Algebraic Languages And How to Reply an Unknown Whistleblower.
David Derler, Daniel Slamanig · 2015
Abstract. Witness encryption (WE) is a recent powerful encryption paradigm. It greatly extends the scope of encryption as it allows to encrypt a message using the description of a hard problem (a word in some language) and someone who knows a solution to this problem (a witness) is able to decrypt. Recent work thereby focuses on constructing WE for NP-complete languages (and thus obtaining WE for any language in NP). While this is an interesting challenge, it is also the main source for inefficiency and requires non-standard assumptions related to multilinear maps and obfuscation. We ask whether it is possible to come up with practically efficient WE schemes, which are still expres-sive enough to provide a solution to the following problem. Assume that an anonymous whistleblower, say Edwarda, wants to leak authoritative secrets in a way that the pub-lic will be convinced of its authenticity, but she wants to stay anonymous. Therefore, she signs the leaked document using a ring signature. Such a signature hides her iden-tity unconditionally among other carefully selected people in an ad-hoc group and does not require getting their approval or assistance. But now the question arises as how to confidentially reply to such an unknown (anonymous) whistleblower.