IACR News item: 26 August 2015
Nishanth Chandran, Srinivasan Raghuraman, Dhinakaran Vinayagamurthy
ePrint Report- A constrained PRF for arbitrary circuit predicates based on (n+l_{OR}-1)-linear maps (where n is the input length and l_{OR} denotes the OR-depth of the circuit).
- For circuits with a specific structure, we also show how to construct such PRFs based on (n+l_{AND}-1)-linear maps (where l_{AND} denotes the AND-depth of the circuit).
- We then give a black-box construction of a constrained PRF for NC1 predicates, from any bit-fixing constrained PRF that fixes only one of the input bits to 1; we only require that the bit-fixing PRF have certain key homomorphic properties. This gives us a constrained PRF for NC1 predicates that is based only on n-linear maps, with no dependence on the predicate.
In contrast, the previous constructions of constrained PRFs (Boneh and Waters, Asiacrypt 2013) required (n+l+1)-linear maps for circuit predicates (where l is the total depth of the circuit) and n-linear maps even for bit-fixing predicates.
- We also show how to extend our techniques to obtain a similar improvement in the case of ABE and construct ABE for arbitrary circuits based on (l_{OR}+1)-linear (respectively (l_{AND}+1)-linear) maps.
Additional news items may be found on the IACR news page.