A communication device comprising: an output unit; a wireless interface; an accepting unit configured to accept an input of user authentication information for authenticating a user of the communication device; an output control unit configured to, in a case where authentication using the inputted user authentication information is successful, cause the output unit to output specific information obtained by using a public key, the public key being obtained by a first external device in response to the specific information being outputted, wherein in a case where the authentication using the inputted user authentication information fails, the specific information is not outputted; a first shifting unit configured to, in a case where the authentication using the inputted user authentication information is successful, shift a state of the communication device from a non-respondent state to a respondent state, wherein in the case where the authentication using the inputted user authentication information fails, the state of the communication device is maintained in the non-respondent state, the non-respondent state being a state where the authentication response is not sent, the respondent state being a state where the authentication response is sent to the first external device in response to the authentication request being received from the first external device; an authentication request receiving unit configured to, after the specific information has been outputted, receive an authentication request in which the public key is used from the first external device via the wireless interface; an authentication response sending unit configured to, in a case where the authentication request is received from the first external device after the state of the communication device has been shifted to the respondent state, send an authentication response to the first external device via the wireless interface; a connection information receiving unit configured to, after the authentication response has been sent to the first external device, receive first connection information from the first external device via the wireless interface, the first connection information being for establishing a first wireless connection via the wireless interface between the communication device and a second external device; and an establishing unit configured to, in a case where the first connection information is received from the first external device, establish the first wireless connection via the wireless interface between the communication device and the second external device by using the first connection information. an output unit; a wireless interface; an accepting unit configured to accept an input of user authentication information for authenticating a user of the communication device; an output control unit configured to, in a case where authentication using the inputted user authentication information is successful, cause the output unit to output specific information obtained by using a public key, the public key being obtained by a first external device in response to the specific information being outputted, wherein in a case where the authentication using the inputted user authentication information fails, the specific information is not outputted; a first shifting unit configured to, in a case where the authentication using the inputted user authentication information is successful, shift a state of the communication device from a non-respondent state to a respondent state, wherein in the case where the authentication using the inputted user authentication information fails, the state of the communication device is maintained in the non-respondent state, the non-respondent state being a state where the authentication response is not sent, the respondent state being a state where the authentication response is sent to the first external device in response to the authentication request being received from the first external device; an authentication request receiving unit configured to, after the specific information has been outputted, receive an authentication request in which the public key is used from the first external device via the wireless interface; an authentication response sending unit configured to, in a case where the authentication request is received from the first external device after the state of the communication device has been shifted to the respondent state, send an authentication response to the first external device via the wireless interface; a connection information receiving unit configured to, after the authentication response has been sent to the first external device, receive first connection information from the first external device via the wireless interface, the first connection information being for establishing a first wireless connection via the wireless interface between the communication device and a second external device; and an establishing unit configured to, in a case where the first connection information is received from the first external device, establish the first wireless connection via the wireless interface between the communication device and the second external device by using the first connection information.