Paper 2010/431

Collusion-Resistant Multicast Key Distribution Based on Homomorphic One-Way Function Trees

Jing Liu and Bo Yang

Abstract

Providing security services for multicast, such as traffic integrity, authentication, and confidentiality, requires securely distributing a group key to group receivers. In the literature, this problem is called multicast key distribution (MKD). A famous MKD protocol—one-way function tree (OFT)—has been found vulnerable to collusion attacks. Solutions to prevent these attacks have been proposed, but at the cost of a higher communication overhead than the original protocol. In this paper, we prove falsity of a recently-proposed necessary and sufficient condition for a collusion attack on the OFT protocol to exist by a counterexample and give a new necessary and sufficient condition for nonexistence of any type of collusion attack on it. We instantiate the general notion of OFT to obtain a particular type of cryptographic construction named homomorphic one-way function tree (HOFT).We propose two structure-preserving graph operations on HOFTs, tree product and tree blinding. One elegant quality possessed by HOFTs is that handling (adding, removing, or changing) leaf nodes in a HOFT can be achieved by using tree product without compromising its structure. We provide algorithms for handling leaf nodes in a HOFT. Employing HOFTs and related algorithms, we put forward a collusion-resistant MKD protocol without losing any communication efficiency compared to the original OFT protocol. We also prove the security of our MKD protocol in a symbolic security model.