A communication system includes a certificate authority for performing authentication, a roadside device, a vehicle-mounted terminal, a first server, and a second server. The vehicle-mounted terminal transmits position information to the first server. The certificate authority acquires information about a vehicle-mounted terminal likely to appear according to place and time from the first server. The certificate authority allows the second server to verify validity of a certificate for a vehicle-mounted terminal acquired from the first server. The certificate authority generates a first list of vehicle-mounted terminals having valid certificates and a second list of vehicle-mounted terminals having invalid certificates according to place and time based on a verification result. The certificate authority transmits the first and second lists to the roadside device and the vehicle-mounted terminal. The roadside device and the vehicle-mounted terminal verify a certificate using the received first and second lists thereby reducing the certificate verification time.