An Independent Set Approach to Solving the Collaborative Attack Problem

A.V.D.M. Kayem, S.G. Akl, and P. Martin (Canada)


Hierarchical access control, distributed databases, security.


Access control in distributed databases has tended to fa vor a hierarchical approach implemented via cryptographic schemes. In such schemes, a central authority generates keys for each level in the hierarchy such that users at a given level can compute, from their own key, the keys of users below them and gain access to information items they hold. Previous schemes proposed, have been found to be either vulnerable to “collaborative attack”1 or inefficient. This paper presents a method of assigning keys at each level in the hierarchy such that the probability of their be ing combined to generate illegal keys is minimized. We model the problem as a graph whose vertices represent the keys generated, and whose edges indicate the probability that their end points can be combined to generate a “col laborative attack”. The concept of independent sets is then used to demonstrate the feasibility of our approach.

Important Links:

Go Back