Space-Efficient Key-Policy Attribute-Based Encryption from Lattices and Two-Dimensional Attributes

Linear secret-sharing scheme (LSSS) is a useful tool for supporting flexible access policy in building attribute-based encryption (ABE) schemes. But in lattice-based ABE constructions, there is a subtle security problem in the sense that careless usage of LSSS-based secret sharing over vectors would lead to the leakage of the master secret key. In this paper, we propose a new method that employs LSSS to build lattice-based key-policy attribute-based encryption (KP-ABE) that resolves this security issue. More specifically, no adversary can reconstruct the master secret key since we introduce a new trapdoor generation algorithm to generate a strong trapdoor (instead of a lattice basis), that is, the master secret key, and remove the dependency of the master secret key on the total number of system attributes. Meanwhile, with the purpose of reducing the storage cost and support dynamic updating on attributes, we extended the traditional 1-dimensional attribute structure to 2-dimensional one. This makes our construction remarkably efficient in space cost, with acceptable time cost. Finally, our scheme is proved to be secure in the standard model.