Generalized key delegation for wildcarded identity-based and inner-product encryption

Inspired by the fact that many e-mail addresses correspond to groups of users, Abdalla introduced the notion of identity-based encryption with wildcards (WIBE), which allows a sender to simultaneously encrypt messages to a group of users matching a certain pattern, defined as a sequence of identity strings and wildcards. This notion was later generalized by Abdalla, Kiltz, and Neven, who considered more general delegation patterns during the key derivation process. Despite its many applications, current constructions have two significant limitations: 1) they are only known to be fully secure when the maximum hierarchy depth is a constant; and 2) they do not hide the pattern associated with the ciphertext. To overcome these, this paper offers two new constructions. First, we show how to convert a WIBE scheme of Abdalla into a (nonanonymous) WIBE scheme with generalized key delegation (WW-IBE) that is fully secure even for polynomially many levels. Then, to achieve anonymity, we initially consider hierarchical predicate encryption (HPE) schemes with more generalized forms of key delegation and use them to construct an anonymous WW-IBE scheme. Finally, to instantiate the former, we modify the HPE scheme of Lewko to allow for more general key delegation patterns. Our proofs are in the standard model and use existing complexity assumptions.