An Independent Set Approach to Solving the Collaborative Attack Problem.
Anne V. D. M. Kayem, Selim G. Akl, Patrick M. Martin · 2005
Access control in distributed databases has tended to favor 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 being 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 “collaborative attack”. The concept of independent sets is then used to demonstrate the feasibility of our approach.