Paper 2020/479

Puncturable Witness Pseudorandom Functions and its Applications on Witness Encryption

Tapas Pal and Ratna Dutta

Abstract

In this work, we propose a slightly stronger variant of witness pseudorandom function (WPRF) defined by Zhandry (TCC 2016), that we call puncturable witness pseudorandom function (pWPRF). It is capable of generating a pseudorandom value corresponding to every statement of an NP language. We utilize the punctured technique to extend applications of WPRF. Specifically, we construct a semi-adaptively secure offline witness encryption (OWE) scheme using a pWPRF, an indistinguishability obfuscation (iO) and a symmetric-key encryption (SKE), which enables us to encrypt messages along with NP statements. We show that replacing iO with extractability obfuscation, the OWE turns out to be an extractable offline witness encryption scheme. To gain finer control over data, we further demonstrate how to convert our OWEs into offline functional witness encryption (OFWE) and extractable OFWE. The ciphertext size of current available OWEs grows polynomially with the size of messages, whereas all of our OWEs produce optimal size ciphertexts. Finally, we show that the WPRF of Pal et al. (ACISP 2019) can be extended to a pWPRF and an extractable pWPRF.