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 c [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 O(k) transmission cost and O(log n) private storage consumption, while the decryption is dominated by 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 O(k) transmission cost and O(logn) private storage consumption. Finally, we also discuss several other promising applications of interval encryption.