International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 26 August 2015

Nishanth Chandran, Srinivasan Raghuraman, Dhinakaran Vinayagamurthy
ePrint Report ePrint Report
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 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.

Expand

Additional news items may be found on the IACR news page.