@inproceedings{chandran2016reducing,
author = {Chandran, Nishanth and Raghuraman, Srinivasan and Vinayagamurthy, Dhinakaran},
title = {Reducing Depth in Constrained PRFs: From Bit-Fixing to NC},
booktitle = {Public Key Cryptography (PKC) 2016},
year = {2016},
month = {March},
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.},
publisher = {Springer},
url = {http://approjects.co.za/?big=en-us/research/publication/reducing-depth-in-constrained-prfs-from-bit-fixing-to-nc/},
pages = {359-385},
edition = {Public Key Cryptography (PKC) 2016},
}