An authentication information providing server includes: a memory configured to store information about vehicles associated with a recipient of a package as a place of delivery, and store pieces of authentication information corresponding to lock/unlock devices each configured to lock or unlock a corresponding one of predetermined compartments of the vehicles; and a processor configured to issue the authentication information to a delivery user terminal based on a request from the delivery user terminal, the delivery user terminal being used by a user who delivers the package, and, when there is a request from the delivery user terminal to set a place of delivery of the package to a vehicle different from a first one of the vehicles, corresponding to the authentication information issued first by the processor, issue the authentication information corresponding to a second one of the vehicles, different from the first one.