Improved (hierarchical) inner-product encryption from lattices

Abstract. 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 twist-ing 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 = Zq. Several applications require the ring R to be exponentially large and, thus, they set q = 2O(n) to implement such applications. This choice results in the AFV IPE scheme with public parameters of size O(µn2 lg3 q) = O(µn5) and ciphertexts of size O(µn lg3 q) = O(µn4), 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(qn) instead of Zq. Our scheme has public parameters of size O(µn2 lg2 q) and ciphertexts of size O(µn lg2 q). Since the cardinality of GF(qn) 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