This invention provides a key distribution system for protecting route-update notifications which overcomes the problem of scalability in the processing of authentication information and achieves a shortening of the time required to verify legitimacy. Its context is a key distribution system for protecting route-update notifications, which distributes, to the routers in a mobile communication network, the authentication information established for mobile terminals, which is used by the routers to authenticate mobile terminal route-update notifications that are communicated from the mobile terminals after encryption. In this context, the invention comprises a top-level router for managing the authentication information of all mobile terminals and for distributing it in response to requests from the routers. These routers are provided with route information management means for holding the authentication information of the mobile terminals, verifying the route-update notifications communicated from these mobile terminals, and managing their route information. This route information management means is provided with means which, if the route information management means does not hold the authentication information corresponding to an originating mobile terminal, requests and acquires the authentication information in question from the top-level router when it receives a route-update notification.