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 4 Feb 2020 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: (Feb. 5th 2020) This paper was subsumed by https://eprint.iacr.org/2020/111 (Jun. 3rd 2019) Modified introduction and added construction for $t$-CNF predicates. Version: 20200205:002638 (All versions of this report) Short URL: ia.cr/2018/982