Optimal Credential Chain Discovery In RT~R System

Role-Based Trust Management System (RBTM) is an effective way to authorization solution in distributed credential management system, and is a hot field in Computer Security. One of the important functionalities of RBTM is to discover a credential chain from given entity to the given role. How to discover such credential chain correctly and efficiently is the core problem in RBTM. Yet the existing RBTM models and credential chain discovery algorithms do not differentiate all the credentials, a credential only could have two states, that either exists in the credential system or not. This is clearly insufficient to precisely describe relationship in reality.In this paper, we first introduce Role-Based Trust Management System with Risk Assessment (RT~R System), i.e. every credential is attached with a risk value that indicates the risk one bears when he/she trusts and relies on the credential. And then we design an Optimal Credential Chain Discovery Algorithm (OCCD) to solve the credential chain discovery problem in RT~R.The OCCD algorithm could find an optimal credential chain connecting the given entity to the given role, with least possible accumulated risk. What's more, it could guarantee polynomial time and space complexity, O(N~4) and O(N~4) respectively, where N is the total number ofcredentials in RT~R.The algorithm is based on the Credential Chain Discovery Framework introduced by Li, et al, and introduces some other data structures, such as priority queue, to solve the optimal risk path problem. In each step, the algorithm could obtain a new optimal path, using priority queue and with some necessary adjustment to the above framework. And also the algorithm keeps track of all the visited role expressions and credentials to avoid redundant process, by how it guarantees the polynomial time and space complexity.