Name
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 $$\\kappa $$ -linear maps for large $$\\kappa $$ . In this work, we focus on the reduction of $$\\kappa $$ in certain constructions of access control primitives that are based on $$\\kappa $$ -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+\\ell _{\\mathsf {OR}}-1-$$ linear maps where n is the input length and $$\\ell _{\\mathsf {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+\\ell _{\\mathsf {AND}}-1-$$ linear maps where $$\\ell _{\\mathsf {AND}}$$ denotes the AND-depth of the circuit. We then give a black-box construction of a constrained PRF for $$\\mathbf {NC}^{1}$$ 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 $$\\mathbf {NC}^{1}$$ 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+\\ell +1-$$ linear maps for circuit predicates where $$\\ell $$ 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 $$\\ell _{\\mathsf {OR}}+1-$$ linear respectively $$\\ell _{\\mathsf {AND}}+1-$$ linear maps. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/978-3-662-49387-8_14 | International Workshop on Practice and Theory in Public Key Cryptography |
Field | DocType | Volume |
Pseudorandom function family,Homomorphic encryption,Discrete mathematics,Boolean circuit,Polynomial,Program obfuscation,Multilinear map,Mathematics,Pseudorandom number generator | Conference | 9615 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
16 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nishanth Chandran | 1 | 0 | 0.34 |
| Srinivasan Raghuraman | 2 | 30 | 3.14 |
| Dhinakaran Vinayagamurthy | 3 | 159 | 5.86 |