Cryptology ePrint Archive: Report 2016/301

Constrained Pseudorandom Functions for Unconstrained Inputs

Apoorvaa Deshpande and Venkata Koppula and Brent Waters

Abstract: A constrained pseudo random function (PRF) behaves like a standard PRF, but with the added feature that the (master) secret key holder, having secret key K, can produce a constrained key, K{f}, that allows for the evaluation of the PRF on all inputs satisfied by the constraint f. Most existing constrained PRF constructions can handle only bounded length inputs. In a recent work, Abusalah et al. [AFP14] constructed a constrained PRF scheme where constraints can be represented as Turing machines with unbounded inputs. Their proof of security, however, requires risky “knowledge type” assumptions such as (public coins) differing inputs obfuscation for circuits and SNARKs.

In this work, we construct a constrained PRF scheme for Turing machines with unbounded inputs under weaker assumptions, namely, the existence of indistinguishability obfuscation for circuits (and DDH).

Category / Keywords:

Original Publication (with minor differences): IACR-EUROCRYPT-2016

Date: received 16 Mar 2016, last revised 19 Aug 2016

Contact author: kvenkata at cs utexas edu

Available format(s): PDF | BibTeX Citation

Note: There was an error in the Eurocrypt 2016 submission (previous version). In this update, we fix it using history-less accumulators/adaptive accumulators.

Version: 20160819:153952 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]