Disclosed herein is a method of verifying key validity and a server for performing the method. The method is configured such that a service provision server verifies key validity in an anonymous service for providing local linkability. The service provision server receives a revocation list. A local revocation list is generated using the received revocation list and a secret key. A virtual index of a service user required to verify key validity is calculated. Whether a key of the service user is valid is verified, based on whether the virtual index is included in the local revocation list.