[Resource Topic] 2018/914: Note on Constructing Constrained PRFs from OWFs with Constant Collusion Resistance

Welcome to the resource topic for 2018/914

Note on Constructing Constrained PRFs from OWFs with Constant Collusion Resistance

Authors: Shuichi Katsumata, Shota Yamada


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.

ePrint: https://eprint.iacr.org/2018/914

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .