Improved subset difference method with ternary tree

Kazuhide Fukushima, Shinsaku Kiyomoto, Toshiaki Tanaka, Kouichi Sakurai

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish
Pages (from-to)2034-2044
Number of pages11
JournalIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Issue number11
Publication statusPublished - Jan 1 2010

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering
  • Applied Mathematics


Dive into the research topics of 'Improved subset difference method with ternary tree'. Together they form a unique fingerprint.

Cite this