Techniques are described for providing enhanced security for electronic communications, such as by including in a message sent between two services a digital signature that is generated by using secret information known to the services, so that the recipient receives assurance regarding the sender's identity if the recipient can replicate the received digital signature using the secret information known to the recipient. In some situations, the enhanced security is used in communications to and/or from an access manager system that provides single sign-on functionality and other functionality to other services for use with those services' users, such as to prevent malicious phishers from inappropriately gaining access to user information. Various services may use the enhanced security techniques when interacting with the access manager system at various times, such as to initiate sign-on for a user and/or to take subsequent action on behalf of a signed-on user.