Paper 2019/1337

Offline Witness Encryption with Semi-Adaptive Security

Peter Chvojka, Tibor Jager, and Saqib A. Kakvi


The first construction of Witness Encryption (WE) by Garg et al. (STOC 2013) has led to many exciting avenues of research in the past years. A particularly interesting variant is Offline WE (OWE) by Abusalah et al. (ACNS 2016), as the encryption algorithm uses neither obfuscation nor multilinear maps. Current OWE schemes provide only selective security. That is, the adversary must commit to their challenge messages $m_0$ and $m_1$ before seeing the public parameters. We provide a new, generic framework to construct OWE, which achieves adaptive security in the sense that the adversary may choose their challenge messages adaptively. We call this semi-adaptive security, because - as in prior work - the instance of the considered NP language that is used to create the challenge ciphertext must be fixed before the parameters are generated in the security proof. We show that our framework gives the first OWE scheme with constant ciphertext overhead even for messages of polynomially-bounded size. We achieve this by introducing a new variant of puncturable encryption defined by Green and Miers (S&P 2015) and combining it with the iO-based approach of Abusalah et al. Finally, we show that our framework can be easily extended to construct the first Extractable Offline Witness Encryption (EOWE), by using extractability obfuscation of Boyle et al. (TCC 2014) in place of iO, opening up even more possible applications. The obfuscation is needed only for our public parameters, but its functionality can be realised with a Trusted Execution Environment (TEE), which means we have a very efficient scheme with ciphertexts consisting of only 5 group elements.

Note: Typo corrections.

Available format(s)
Publication info
Published elsewhere. Major revision. ACNS 2020
Witness encryptionfunctional encryptionobfuscationprovable security
Contact author(s)
chvojka @ uni-wuppertal de
jager @ uni-wuppertal de
kakvi @ uni-wuppertal de
2020-10-14: last of 2 revisions
2019-11-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Peter Chvojka and Tibor Jager and Saqib A.  Kakvi},
      title = {Offline Witness Encryption with Semi-Adaptive Security},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1337},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.