Paper 2015/249

Improved (Hierarchical) Inner-Product Encryption from Lattices

Keita Xagawa

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 twisting the identity-based encryption (IBE) scheme by Agrawal, Boneh, and Boyen~(Eurocrypt 2010). Their IPE scheme supports inner-product predicates over $R^{\mu }$, where the ring is $R={\mathbb{Z}}_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 $$ where $$ instead of $$. Our scheme has public parameters of size $$ and ciphertexts of size $$. Since the cardinality of $$ is inherently exponential in $$, we have no need to set $$ 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.

Note: This is the full version.