How to Construct Interval Encryption from Binary Tree Encryption

In a broadcast encryption system with a total of

n

users, each user is assigned with a unique index

i

 ∈ [1,

n

]. An encryptor can choose a receiver set

S

 ⊆ [1,

n

] freely and encrypt a message for the recipients in

S

such that only those receivers can open the message. The transmission overload of most previous broadcast encryption systems grows in line with the number of revoked users

r

and thus they are suitable for the scenario where the target receiver set is large when

r

 ≪ 

n

holds. Some other recently proposed constructions for arbitrary receiver set require a unreasonably large user storage and long decryption time. On the other hand, it is observed that, in a practical broadcast encryption system, the receiver set can be regarded as a collection of

k

natural intervals, where the interval number

k

should be much less than

r

for most cases. This observation motivates us to introduce a novel type of encryption, called interval encryption, which could realize a more efficient broadcast encryption. To achieve this, we first present a generic way to transform a binary tree encryption scheme into interval encryption. One concrete instantiation of this method based on the hierarchical identity based encryption scheme by Boneh et al. only requires a

$\mathcal{O}(k)$

transmission cost and

$\mathcal{O}(\log n)$

private storage consumption, while the decryption is dominated by

$\mathcal{O}(\log n)$

group operations. With detailed performance analysis, we demonstrate that the proposed interval encryption strategy has the superiority on improved efficiency and thus is expected to serve as a more efficient solution in more cases than the traditional systems in practice. Interestingly, our methodology can also be employed to transform a fully secure hierarchical identity based encryption scheme proposed by Lewko and Waters into an adaptively secure interval encryption scheme with a

$\mathcal{O}(k)$

transmission cost and

$\mathcal{O}(\log n)$

private storage consumption. Finally, we also discuss several other promising applications of interval encryption.