Complexity of credential processing

Role-based Trust management (RT) languages are an effective means for describing security policies in decentralized and open environments. The statements of a RT language are credentials that describe entities and roles, which the entities can play in the system. A set of credentials can define the security policy and allow deciding on who is authorized to access a resource, and who is not. A credential graph is a graphical representation of the semantics of a given set of credentials. Making a decision on the membership of an entity in a role is equivalent to checking whether an appropriate path exists in the graph. The core part of this paper is a definition of an algorithm for building a credential graph for a set of RT^T credentials, and an evaluation of the complexity of the graph building process.