Cryptology ePrint Archive: Report 2018/982

Constrained PRFs for Bit-fixing (and More) from OWFs with Adaptive Security and 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 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.

Category / Keywords: foundations / Constrained PRF, Adaptive security, Collusion-resistance, One-way functions

Date: received 12 Oct 2018, last revised 3 Jun 2019

Contact author: alex davidson 2014 at rhul ac uk,shuichi katsumata000@gmail com,ryo nishimaki@gmail com,shota yamada enc@gmail com

Available format(s): PDF | BibTeX Citation

Note: Modified introduction and added construction for $t$-CNF predicates.

Version: 20190603:085612 (All versions of this report)

Short URL: ia.cr/2018/982