**Reducing Depth in Constrained PRFs: From Bit-Fixing to NC1**

*Nishanth Chandran and Srinivasan Raghuraman and Dhinakaran Vinayagamurthy*

**Abstract: **The candidate construction of multilinear maps by Garg, Gentry, and Halevi (Eurocrypt 2013) has lead to an explosion of new cryptographic constructions ranging from attribute-based encryption (ABE) for arbitrary polynomial size circuits, to program obfuscation, and to constrained pseudorandom functions (PRFs). Many of these constructions require k-linear maps for large k. In this work, we focus on the reduction of k in certain constructions of access control primitives that are based on k-linear maps; in particular, we consider the case of constrained PRFs and ABE. We construct the following objects:

- 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 construction is of independent interest as it sheds light on the hardness of constructing constrained PRFs even for ``simple'' predicates such as bit-fixing predicates.

Instantiating this construction with the bit-fixing constrained PRF from Boneh and Waters (Asiacrypt 2013) 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.

**Category / Keywords: **Constrained PRFs, multilinear maps, ABE

**Original Publication**** (with minor differences): **IACR-PKC-2016

**Date: **received 26 Aug 2015, last revised 31 Dec 2015

**Contact author: **dhinakaran2705 at gmail com

**Available format(s): **PDF | BibTeX Citation

**Note: **Full version of the paper published in PKC 2016.

**Version: **20151231:162655 (All versions of this report)

**Short URL: **ia.cr/2015/829

[ Cryptology ePrint archive ]