Numerous services are being offered over the Internet and require identification of users as in face-to-face interactions. To simplify the authentication procedure and reduce the need to manage multiple credentials to access services, Electronic Identification (eID) schemes have been introduced. eID schemes commonly involve many service providers (SPs) which provide services, such as online shopping, social networks, etc. to users and identity providers (IDPs) which verify the identity of users and facilitate the users to authenticate him/herself to SPs. In federated eID schemes, IDPs store identifiable user information (attributes), often with a unique ID, and attest on these attributes to SPs. In this work we address the privacy concerns of storing user attributes at the IDP which allows the IDP to profile the behaviour and activities of users. We propose to store the attributes in a privacy friendly manner so that they cannot be directly linked to a particular user even if the data is leaked. Then we include an additional step incorporating private information retrieval (PIR) in the usual authentication flow of federated eID scheme so that the IDP can perform its role of authenticating and managing the user’s identity without turning into a privacy hotspot. The privacy enhancement offered by our work needs to be accompanied by privacy-friendly authentication, which does not reveal the identity of the user, to be effective. Finally, through a proof-of-concept implementation we show a practical variant of our scheme in which the IDP, with millions of users, partitions its database.