Improved Subset Difference Method with Ternary Tree

Kazuhide FUKUSHIMA  Shinsaku KIYOMOTO  Toshiaki TANAKA  Kouichi SAKURAI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E93-A   No.11   pp.2034-2044
Publication Date: 2010/11/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E93.A.2034
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)
Category: Cryptography and Information Security
broadcast encryption,  subset difference method,  ternary tree,  

Full Text: PDF>>
Buy this Article

This paper proposes a ternary subset difference method (SD method) that is resistant to coalition attacks. In order to realize a secure ternary SD method, we design a new cover-finding algorithm, label assignment algorithm and encryption algorithm. These algorithms are required to revoke one or two subtrees simultaneously while maintaining resistance against coalition attacks. We realize this two-way revocation mechanism by creatively using labels and hashed labels. Then, we evaluate the efficiency and security of the ternary SD method. We show that the number of labels on each client device can be reduced by about 20.4 percent. The simulation results show that the proposed scheme reduces the average header length by up to 15.0 percent in case where the total number of devices is 65,536. On the other hand, the computational cost imposed on a client device stays within O(log n). Finally, we prove that the ternary SD method is secure against coalition attacks.