Paper 2018/982

Constrained PRFs for Bit-fixing from OWFs with Constant Collusion Resistance

Alex Davidson and Shuichi Katsumata and Ryo Nishimaki and Shota Yamada

Abstract

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, a requirement for all 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 predicates. CPRFs from more standard assumptions only satisfy security for a single constrained key query. In this work, we give the first construction of a CPRF that can issue a constant number of constrained keys for bit-fixing 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), and that it also achieves fully adaptive security. This is the only construction to achieve adaptive security outside of the random oracle model, and without sub-exponential security losses. Our technique represents a noted departure from existing CPRF constructions. We hope that it may lead to future constructions that can expose a greater number of keys, or consider more expressive predicates (such as bounded-depth circuit constraints).

Note: Revised the future works part.