TY - GEN
T1 - How to construct interval encryption from binary tree encryption
AU - Lin, Huang
AU - Cao, Zhenfu
AU - Liang, Xiaohui
AU - Zhou, Muxin
AU - Zhu, Haojin
AU - Xing, Dongsheng
PY - 2010
Y1 - 2010
N2 - 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 κ natural intervals, where the interval number κ 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(κ) 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(κ) transmission cost and O(log n) private storage consumption. Finally, we also discuss several other promising applications of interval encryption.
AB - 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 κ natural intervals, where the interval number κ 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(κ) 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(κ) transmission cost and O(log n) private storage consumption. Finally, we also discuss several other promising applications of interval encryption.
KW - Binary tree encryption
KW - Hierarchical IBE
KW - Interval encryption
KW - Public key broadcast encryption
UR - https://www.scopus.com/pages/publications/79956295030
U2 - 10.1007/978-3-642-13708-2_2
DO - 10.1007/978-3-642-13708-2_2
M3 - 会议稿件
AN - SCOPUS:79956295030
SN - 3642137075
SN - 9783642137075
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 19
EP - 34
BT - Applied Cryptography and Network Security - 8th International Conference, ACNS 2010, Proceedings
T2 - 8th International Conference on Applied Cryptography and Network Security, ACNS 2010
Y2 - 22 June 2010 through 25 June 2010
ER -