Technologies for distributed single sign-on operable to provide user access to a plurality of services via authentication to a single entity. The distributed single sign-on technologies provide a set of authentication servers and methods for privacy protection based on splitting secret keys and user profiles into secure shares and periodically updating shares among the authentication servers without affecting the underlying secrets. The correctness of the received partial token or partial profiles can be verified with non-interactive zero-knowledge proofs.