A communication device stores a first secret key and a first public key, and the on-vehicle authentication device stores a second secret key, a second public key and a signature verification key. The on-vehicle authentication device acquires the first public key, verifies the authenticity of the electronic signature using a signature verification key, encrypts the second public key using the authentic first public key and transmits the encrypted second public key. The communication device receives the encrypted second public key, decrypts the encrypted second public key using the first secret key, encrypts the first public key using the decrypted second public key. The on-vehicle authentication device receives the encrypted first public key, decrypts the encrypted first public key using the second secret key, and authenticates that the communication device is an authentic device when the decrypted first public key has been determined to be authentic.