Constrained Pseudorandom Functions for Unconstrained Inputs

Apoorvaa Deshpande; Venkata Koppula; Brent Waters

Paper 2016/301

Constrained Pseudorandom Functions for Unconstrained Inputs

Apoorvaa Deshpande, 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).

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

Metadata

Available format(s): PDF
Publication info: A minor revision of an IACR publication in EUROCRYPT 2016
Contact author(s): kvenkata @ cs utexas edu
History: 2016-08-19: last of 3 revisions; 2016-03-17: received; See all versions
Short URL: https://ia.cr/2016/301
License: CC BY

BibTeX

@misc{cryptoeprint:2016/301,
      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},
      url = {https://eprint.iacr.org/2016/301}
}