A COLLUSION PROBLEM AND ITS SOLUTION

Consider a group of colluders, each with certain knowledge such as the identity of some other colluders, some cryptographic keys, and some d ata, possibly multiply encrypted. Two colluders can combine their know ledge if their current knowledge satisfies certain conditions. Their c ryptographic keys can help decrypt each other's encrypted data, expand ing their knowledge and revealing more collusion opportunities, and th e process of collusion continues. The question we address is whether i t is possible for the colluders to uncover a target set of unencrypted data. In this paper we formulate the collusion problem and provide an algorithm that determines whether a collusion problem has a solution and, if so, computes one. A solution is a specific way by which the co lluders can uncover the hidden information. The solution generated by our algorithm is generally not one that involves the minimum number of colluders. We show, however, that to find such a solution is NP-compl ete. Complex communications protocols employing cryptographic building blocks are being developed to transfer information among some users a nd hide from others. The algorithm presented here can be applied to de termine whether and how a subset of protocol users can discover during or after the protocol's execution the information that is to be hidde n from them. (C) 1998 Academic Press.