OpenID Connect is the most widely used Internet protocol for
delegated authentication today. It provides single sign-on
functionality for users who use their account with an identity
provider to authenticate to different services, called relying
parties.  Unfortunately OpenID Connect is not privacy-friendly:
the identity provider learns with each use which relying party
the user logs in to. This necessitates a high degree of trust in
the identity provider, and is especially problematic when the
relying parties' identity reveals sensitive information.

We present two extensions to OpenID Connect that address this
privacy concern. We first present a simple extension that
prevents the identity provider from learning to which relying
parties its users log in, and then further extend this solution
to also prevent colluding relying parties from tracking users.
We give formal security proofs for both standard OpenID Connect
and our extensions using the Tamarin security protocol
verification tool.