The first authentication unit of an authentication apparatus decides whether first authentication data exists in a received message, and performs, if it is decided that the first authentication data exists, authentication based on the first authentication data. The second authentication unit of the authentication apparatus decides whether second authentication data exists in the received message, and performs, if it is decided that the second authentication data exists, authentication based on the second authentication data. If the second authentication unit decides that no second authentication data exists in the received message, and the first authentication unit decides that authentication has succeeded, it is decided that authentication for the received message has succeeded.