ABE with tag made easy: Concise framework and new instantiations in prime-order groups

Among all existing identity-based encryption (IBE) schemes in the bilinear group, Wat - IBE proposed by Waters [CRYPTO, 2009] and JR - IBE proposed by Jutla and Roy [AsiaCrypt, 2013] are quite special. A secret key and/or ciphertext in these two schemes consist of several group elements and an integer which is usually called tag. A series of prior work was devoted to extending them towards more advanced attribute-based encryption (ABE) including inner-product encryption (IPE), hierarchical IBE (HIBE). Recently, Kim et al. [SCN, 2016] introduced the notion of tag-based encoding and presented a generic framework for extending Wat - IBE. We may call these ABE schemes ABE with tag or tag-based ABE. Typically, a tag-based ABE construction is more efficient than its counterpart without tag. However the research on tag-based ABE severely lags—We do not know how to extend JR - IBE in a systematic way and there is no tag-based ABE for boolean span program even with Kim et al.’s generic framework. In this work, we proposed a generic framework for tag-based ABE which is based on JR - IBE and compatible with Chen et al.’s (attribute-hiding) predicate encoding [EuroCrypt, 2015]. The adaptive security in the standard model relies on the k-linear assumption in the asymmetric prime-order bilinear group. This is the first framework showing how to extend JR - IBE systematically. In fact our framework and its simple extension are able to cover most concrete tag-based ABE constructions in previous literature. Furthermore, since Chen et al.’s predicate encoding supports a large number of predicates including boolean span program, we can now give the first (both key-policy and ciphertext-policy) tag-based ABE for boolean span program in the standard model. Technically our framework is based on a simplified version of JR - IBE. Both the description and its proof are quite similar to the prime-order IBE derived from Chen et al.’s framework. This not only allows us to work with Chen et al.’s predicate encoding but also provides us with a clear explanation of JR - IBE and its proof technique.