An information holding medium stores the common key of the user used in the common-key encryption method. In response to a user authentication request sent from an information processing apparatus, the user is authenticated by the common-key encryption method by using the common key stored in the information holding medium of the user. Only when the user has been authenticated, predetermined processing for making the information processing apparatus authenticate the user by the public-key encryption method is performed.