**Constrained PRFs for Bit-fixing (and More) from OWFs with Adaptive Security and Constant Collusion Resistance.** / Davidson, Alexander; Katsumata, Shuichi; Nishimaki, Ryo; Yamada, Shota.

Research output: Contribution to journal › Article

Published

**Constrained PRFs for Bit-fixing (and More) from OWFs with Adaptive Security and Constant Collusion Resistance.** / Davidson, Alexander; Katsumata, Shuichi; Nishimaki, Ryo; Yamada, Shota.

Research output: Contribution to journal › Article

Davidson, A, Katsumata, S, Nishimaki, R & Yamada, S 2018, 'Constrained PRFs for Bit-fixing (and More) from OWFs with Adaptive Security and Constant Collusion Resistance', *IACR Cryptology ePrint Archive*, vol. 2018, no. 982, pp. 1-28. <https://eprint.iacr.org/2018/982>

Davidson, A., Katsumata, S., Nishimaki, R., & Yamada, S. (2018). Constrained PRFs for Bit-fixing (and More) from OWFs with Adaptive Security and Constant Collusion Resistance. *IACR Cryptology ePrint Archive*, *2018*(982), 1-28. https://eprint.iacr.org/2018/982

Davidson A, Katsumata S, Nishimaki R, Yamada S. Constrained PRFs for Bit-fixing (and More) from OWFs with Adaptive Security and Constant Collusion Resistance. IACR Cryptology ePrint Archive. 2018 Oct 12;2018(982):1-28.

@article{96851a60f466460a88de5a1094e81e86,

title = "Constrained PRFs for Bit-fixing (and More) from OWFs with Adaptive Security and Constant Collusion Resistance",

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. ",

author = "Alexander Davidson and Shuichi Katsumata and Ryo Nishimaki and Shota Yamada",

year = "2018",

month = oct,

day = "12",

language = "English",

volume = "2018",

pages = "1--28",

journal = "IACR Cryptology ePrint Archive",

number = "982",

}

TY - JOUR

T1 - Constrained PRFs for Bit-fixing (and More) from OWFs with Adaptive Security and Constant Collusion Resistance

AU - Davidson, Alexander

AU - Katsumata, Shuichi

AU - Nishimaki, Ryo

AU - Yamada, Shota

PY - 2018/10/12

Y1 - 2018/10/12

N2 - 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.

AB - 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.

M3 - Article

VL - 2018

SP - 1

EP - 28

JO - IACR Cryptology ePrint Archive

JF - IACR Cryptology ePrint Archive

IS - 982

ER -