Improved (Hierarchical) Inner-Product Encryption from Lattices

Inner-product encryption (IPE) provides fine-grained access control and has attractive applications. Agrawal, Freeman, and Vaikuntanathan (Asiacrypt 2011) proposed the first IPE scheme from lattices by twisting the identity-based encryption (IBE) scheme by Agrawal, Boneh, and Boyen (Eurocrypt 2010). Their IPE scheme supports inner-product predicates over

R

μ

, where the ring is

R

 = ℤ

q

. Several applications require the ring

R

to be exponentially large and, thus, they set

q

 = 2

O

(

n

)

to implement such applications. This choice results in the AFV IPE scheme with public parameters of size

$O(\mu n^2 \lg^3{q}) = O(\mu n^5)$

and ciphertexts of size

$O(\mu n \lg^3{q}) = O(\mu n^4)$

, where

n

is the security parameter. Hence, this makes the scheme impractical, as they noted.

We address this efficiency issue by “untwisting” their twist and providing another twist. Our scheme supports inner-product predicates over

R

μ

where

R

 = GF(

q

n

) instead of ℤ

q

. Our scheme has public parameters of size

$O(\mu n^2 \lg^2{q})$

and ciphertexts of size

$O(\mu n \lg^2{q})$

. Since the cardinality of GF(

q

n

) is inherently exponential in

n

, we have no need to set

q

as the exponential size for applications.

As side contributions, we extend our IPE scheme to a hierarchical IPE (HIPE) scheme and propose a fuzzy IBE scheme from IPE. Our HIPE scheme is more efficient than that developed by Abdalla, De Caro, and Mochetti (Latincrypt 2012). Our fuzzy IBE is secure under a much weaker assumption than that employed by Agrawal et al. (PKC 2012), who constructed the first lattice-based fuzzy IBE scheme.