Paper 2018/890

A Bit-fixing PRF with O(1) Collusion-Resistance from LWE

Alex Davidson and Ryo Nishimaki

Abstract

Constrained pseudorandom functions (CPRFs) allow learning modified 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 [Asiacrypt 2013], 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, a requirement for all of these applications. Unfortunately, existing constructions of CPRFs satisfying this security notion are only known from exceptionally strong cryptographic assumptions, such as indistinguishability obfuscation and the existence of multilinear maps, even for very weak predicates. CPRFs from more standard assumptions only satisfy security when one key is learnt. In this work, we give the first construction of a CPRF that can issue a constant number of constrained keys for bit-fixing predicates, from learning with errors (LWE). It also satisfies \(1\)-key privacy (otherwise known as constraint-hiding). Finally, our construction achieves fully adaptive security with polynomial security loss; the only construction to achieve such security under a standard assumption. Our technique represents a noted departure existing for CPRF constructions. We hope that it may lead to future constructions that can expose a greater number of keys, or consider more expressive predicates (such as circuit-based constraints).

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 $O(1)$ collusion-resistance from OWFs.