While federated identity management separates service provisioning from identity provisioning, the identity provider is usually operated at the home organization of the identities. We address the challenge of outsourcing the entire identity provider with its user database to an untrusted external provider in a secure and privacy-preserving way. With this type of outsourcing, the home organization is no longer required to operate high availability infrastructure for access management. Instead, the home organization only needs to frequently attest that the identity data in the outsourced database is still up to date, a task that is much less demanding than providing access decisions whenever a user wants to make use of a service. In this paper we present Occasio, a concept that permits secure outsourcing of identity and access management to untrusted external providers. Occasio builds on concepts of outsourcing databases and particularly on Merkle Hash Trees. We show that Occasio matches all security requirements for operation in an untrusted environment. Furthermore, we demonstrate that Occasio can be easily integrated into the SAML ... mehrstandard. We present results of a performance evaluation that shows that Occasio behaves well in terms of overhead. Finally, we show that with Occasio identity data of different home organizations can be ‘aggregated’ without being linkable by someone other than the services that are granted to do so by the user.