Paper 2015/1073

Practical Witness Encryption for Algebraic Languages Or How to Encrypt Under Groth-Sahai Proofs

David Derler and Daniel Slamanig


Witness encryption (WE) is a recent powerful encryption paradigm, which allows to encrypt a message using the description of a hard problem (a word in an NP-language) and someone who knows a solution to this problem (a witness) is able to efficiently decrypt the ciphertext. Recent work thereby focuses on constructing WE for NP complete languages (and thus NP). While this rich expressiveness allows flexibility w.r.t. applications, it makes existing instantiations impractical. Thus, it is interesting to study practical variants of WE schemes for subsets of NP that are still expressive enough for many cryptographic applications. We show that such WE schemes can be generically constructed from smooth projective hash functions (SPHFs). In terms of concrete instantiations of SPHFs (and thus WE), we target languages of statements proven in the popular Groth-Sahai (GS) non-interactive witness-indistinguishable/zero-knowledge proof framework. This allows us to provide a novel way to encrypt. In particular, encryption is with respect to a GS proof and efficient decryption can only be done by the respective prover. The so obtained constructions are entirely practical. To illustrate our techniques, we apply them in context of privacy-preserving exchange of information.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Minor revision. Designs, Codes and Cryptography
witness encryptionsmooth projective hash functionsGroth-Sahai proofsencryptionprivacy
Contact author(s)
david derler @ iaik tugraz at
2018-01-09: last of 6 revisions
2015-11-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {David Derler and Daniel Slamanig},
      title = {Practical Witness Encryption for Algebraic Languages Or How to Encrypt Under Groth-Sahai Proofs},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1073},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.