Paper 2016/301

Constrained Pseudorandom Functions for Unconstrained Inputs

Apoorvaa Deshpande, Venkata Koppula, and Brent Waters


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).

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

Available format(s)
Publication info
A minor revision of an IACR publication in EUROCRYPT 2016
Contact author(s)
kvenkata @ cs utexas edu
2016-08-19: last of 3 revisions
2016-03-17: received
See all versions
Short URL
Creative Commons Attribution


      author = {Apoorvaa Deshpande and Venkata Koppula and Brent Waters},
      title = {Constrained Pseudorandom Functions for Unconstrained Inputs},
      howpublished = {Cryptology ePrint Archive, Paper 2016/301},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.