The present invention extends to methods, systems, and computer program products for modeling party identities in computer storage systems. A federated identity fabric models identity data and relationships between portions of indentify data in computer storage systems in accordance with a uniform schema. The federated identity fabric can federate distributed identity and identity relationship data from computer storage systems within the variety of different computing environments. Code and metadata at computing environments associated with the federated identity fabric can interoperate to facilitate uniformly storing, accessing, modifying, deleting, and securing identity and identity relationship data within the federated identify fabric. Embodiments of the invention include utilizing an identity key table entry to locate party identity information and performing key transformations between different types of identity keys.