**Constructing Witness PRF and Offline Witness Encryption Without Multilinear Maps**

*Tapas Pal and Ratna Dutta*

**Abstract: **Witness pseudorandom functions (witness PRFs), introduced by Zhandry [Zha16], was defined for an NP language L and generate a pseudorandom value for any instance x. The same pseudorandom value can be obtained efficiently using a valid witness w for x belongs to L. Zhandry built a subset-sum encoding scheme from multilinear maps and then converted a relation circuit corresponding to an NP language L to a subset-sum instance to achieve a witness PRF for L. The main goal in developing witness PRF in [Zha16] is to avoid obfuscation from various constructions of cryptographic primitives. Reliance on cryptographic tools built from multilinear maps may be perilous as existing multilinear maps are still heavy
tools to use and suffering from many non-trivial attacks.

In this work, we give constructions of the following cryptographic primitives without using multilinear maps and instantiating obfuscation from randomized encoding:

– We construct witness PRFs using a puncturable pseudorandom function and sub-exponentially secure randomized encoding scheme in common reference string (CRS) model. A sub-exponentially secure randomized encoding scheme in CRS model can be achieved from a sub-exponentially secure public key functional encryption scheme and learning with error assumptions with sub-exponential hardness.

– We turn our witness PRF into a multi-relation witness PRF where one can use the scheme with a class of relations related to an NP language.

– Furthermore, we construct an offline witness encryption scheme using any extractable witness PRF. The offline witness encryption scheme of Abusalah et al. [AFP16] was built from a plain public-key encryption, a statistical simulation-sound non-interactive zero knowledge (SSS-NIZK) proof system and obfuscation. In their scheme, a(n) SSS-NIZK proof is needed for the encryption whose efficiency depends on the underlying public key encryption. We replace SSS-NIZK by extractable witness PRF and construct an offline witness encryption scheme. More precisely, our scheme is based on a public-key encryption, a witness PRF and employs a sub-exponentially secure randomized encoding scheme in CRS model instantiating obfuscation. Our offline witness encryption can be turned into an offline functional witness encryption scheme where decryption releases a function of a message and witness as output.

**Category / Keywords: **Witness PRF, Offline witness encryption, Randomized encoding.

**Date: **received 7 Jun 2018, last revised 25 Jun 2018

**Contact author: **tapas pal at iitkgp ac in, ratna@maths iitkgp ernet in

**Available format(s): **PDF | BibTeX Citation

**Version: **20180625:135656 (All versions of this report)

**Short URL: **ia.cr/2018/587

[ Cryptology ePrint archive ]