1. A method for a computing system of a single sign-on service to verify identities of third-party Web sites whose users interact with the single sign-on service, the verifying being based in part on use of digital signatures corresponding to the Web sites, the method comprising: for each of multiple third-party Web sites, registering the Web site with the single sign-on service, the registering including obtaining information for the Web site that includes a shared secret access key available to the Web site and a unique non-secret identifier associated with the shared secret access key; receiving multiple sign-on messages that are each from one of the multiple third-party Web sites on behalf of a user of the one Web site who is attempting to perform a sign-on to the single sign-on service, each message including multiple parameters that identify the user and that indicate sign-on information for the user, each message further including the identifier of the one Web site and a digital signature that is generated using the shared secret access key of the one Web site and using information included in the message; and for each of the multiple received sign-on messages, verifying an identity of the Web site from which the sign-on message was received based at least in part on the digital signature included in the sign-on message.