Method, server, and communication device for updating identity-based cryptographic private keys of compromised communication devices. One method includes receiving, at a server, a security status indicating that the security of a first communication device has been compromised. The first communication device is associated with a user and includes a first identity-based cryptographic private key and a first user identifier. The method also includes, responsive to receiving the security status, determining, with the server, a second user identifier based on the first user identifier. The method further includes determining, with the server, a second identity-based cryptographic private key based on the second user identifier. The method also includes distributing, via the server, the second identity-based cryptographic private key to a second communication device. The second communication device is associated with the user.