Paper 2018/914

Note on Constructing Constrained PRFs from OWFs with Constant Collusion Resistance

Shuichi Katsumata and Shota Yamada

Abstract

Constrained pseudorandom functions (CPRFs) are a type of PRFs that allows one to derive a constrained key $\mathsf{K}_C$ from the master key $\mathsf{K}$. While the master key $\mathsf{K}$ allows one to evaluate on any input as a standard PRF, the constrained key $\mathsf{K}_C$ only allows one to evaluate on inputs $x$ such that $C(x) = 1$. Since the introduction of CPRFs by Boneh and Waters (ASIACRYPT'13), Kiayias et al. (CCS'13), and Boyle et al. (PKC'14), there have been various constructions of CPRFs. However, thus far, almost all constructions (from standard assumptions and non-trivial constraints) are only proven to be secure if at most one constrained key $\mathsf{K}_C$ is known to the adversary, excluding the very recent work of Davidson and Nishimaki (EPRINT'18). Considering the interesting applications of CPRFs such as ID-based non-interactive key exchange, we desire CPRFs that are collusion resistance with respect to the constrained keys. In this work, we make progress in this direction and construct a CPRF for the bit-fixing predicates that are collusion resistance for a constant number of constrained keys. Surprisingly, compared to the heavy machinery that was used by previous CPRF constructions, our construction only relies on the existence of one-way functions.

Note: This is an out of date draft and here reference only. This work was superseded and replaced with the paper "Constrained PRFs for Bit-fixing from OWFs with Constant Collusion Resistance" by Davidson, Katsumata, Nishimaki, and Yamada (eprint report 2018/982), which achieves a bit-fixing PRF with constant collusion-resistance and key-privacy from OWFs.