Cryptology ePrint Archive: Report 2019/1337

Offline Witness Encryption with Semi-Adaptive Security

Peter Chvojka and Tibor Jager and Saqib A. Kakvi

Abstract: 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.

Category / Keywords: foundations / Witness encryption, functional encryption, obfuscation, provable security

Original Publication (with major differences): ACNS 2020

Date: received 20 Nov 2019, last revised 14 Oct 2020

Contact author: chvojka at uni-wuppertal de, jager at uni-wuppertal de, kakvi at uni-wuppertal de

Available format(s): PDF | BibTeX Citation

Note: Typo corrections.

Version: 20201014:192408 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]