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 data, possibly multiply encrypted. Two colluders can combine their knowledge if their current knowledge satisfies certain conditions. Their cryptographic keys can help decrypt each other's encrypted data, expanding their knowledge and revealing more collusion opportunities, and the process of collusion continues. The question we address is whether it 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 colluders 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-complete. Complex communications protocols employing cryptographic building blocks are being developed to transfer information among some users and hide from others. The algorithm presented here can be applied to determine whether and how a subset of protocol users can discover during or after the protocol's execution the information that is to be hidden from them.