Paper 2018/982

Constrained PRFs for Bit-fixing (and More) from OWFs with Adaptive Security and Constant Collusion Resistance

Alex Davidson, Shuichi Katsumata, Ryo Nishimaki, and Shota Yamada


Constrained pseudorandom functions (CPRFs) allow learning "constrained" PRF keys that can evaluate the PRF on a subset of the input space, or based on some sort of predicate. First introduced by Boneh and Waters [AC'13], Kiayias et al. [CCS'13] and Boyle et al. [PKC'14], they have been shown to be a useful cryptographic primitive with many applications. The full security definition of CPRFs requires the adversary to learn multiple constrained keys in an arbitrary order, a requirement for many of these applications. Unfortunately, existing constructions of CPRFs satisfying this security notion are only known from exceptionally strong cryptographic assumptions, such as indistinguishability obfuscation (IO) and the existence of multilinear maps, even for very weak constraints. CPRFs from more standard assumptions only satisfy selective security for a single constrained key query. In this work, we give the first construction of a CPRF that can adaptively issue a constant number of constrained keys for bit-fixing predicates (or more generally $t$-conjunctive normal form predicates), only requiring the existence of one-way functions (OWFs). This is a much weaker assumption compared with all previous constructions. In addition, we prove that the new scheme satisfies 1-key privacy (otherwise known as constraint-hiding). This is the only construction for any non-trivial predicates to achieve adaptive security and collusion-resistance outside of the random oracle model or relying on strong cryptographic assumptions. Our technique represents a noted departure from existing CPRF constructions.

Note: (Feb. 5th 2020) This paper was subsumed by (Jun. 3rd 2019) Modified introduction and added construction for $t$-CNF predicates.

Available format(s)
Publication info
Preprint. MINOR revision.
Constrained PRFAdaptive securityCollusion-resistanceOne-way functions
Contact author(s)
alex davidson 2014 @ rhul ac uk
shuichi katsumata000 @ gmail com
ryo nishimaki @ gmail com
shota yamada enc @ gmail com
2020-02-05: last of 3 revisions
2018-10-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Alex Davidson and Shuichi Katsumata and Ryo Nishimaki and Shota Yamada},
      title = {Constrained PRFs for Bit-fixing (and More) from OWFs with Adaptive Security and Constant Collusion Resistance},
      howpublished = {Cryptology ePrint Archive, Paper 2018/982},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.